fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. //Find the nearest smaller numbers on left side in an array
  8. //http://w...content-available-to-author-only...s.org/find-the-nearest-smaller-numbers-on-left-side-in-an-array/
  9.  
  10. /* Name of the class has to be "Main" only if the class is public. */
  11. class Ideone
  12. {
  13. 	public static void main (String[] args) throws java.lang.Exception
  14. 	{
  15. 		int[] arr = new int[] { 1, 3, 0, 2, 5 };
  16. 		printArray(arr);
  17. 		System.out.println("");
  18. 		printArray(nearestSmallestOnLeftSideInArray(arr));
  19. 	}
  20.  
  21. 	private static void printArray(int[] arr) {
  22. 		System.out.println("");
  23. 		System.out.println("TestSort.printArray()");
  24. 		for (int i = 0; i < arr.length; i++) {
  25. 			System.out.print(arr[i] + " ");
  26. 		}
  27. 	}
  28.  
  29. 		private static int[] nearestSmallestOnLeftSideInArray(int[] arr) {
  30. 		Stack<Integer> stack = new Stack<>();
  31. 		int nearestSmallest[] = new int[arr.length];
  32.  
  33. 		stack.push(arr.length - 1);
  34.  
  35. 		for (int i = arr.length - 2; i >= 0; i--) {
  36. 			if (stack.peek() != null) {
  37. 				while (true) {
  38. 					if (stack.isEmpty() || arr[i] > arr[stack.peek()]) {
  39. 						break;
  40. 					}
  41. 					nearestSmallest[stack.pop()] = arr[i];
  42. 				}
  43. 			}
  44. 			stack.push(i);
  45. 		}
  46.  
  47. 		while (!stack.isEmpty()) {
  48. 			nearestSmallest[stack.pop()] = -1;
  49. 		}
  50.  
  51. 		return nearestSmallest;
  52. 	}
  53.  
  54.  
  55. }
Success #stdin #stdout 0.17s 33584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
TestSort.printArray()
1 3 0 2 5 

TestSort.printArray()
-1 1 -1 0 2
https://ideone.com/vnzIEe
language:
Java (HotSpot 12)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!