/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
//Find the nearest smaller numbers on left side in an array
//http://w...content-available-to-author-only...s.org/find-the-nearest-smaller-numbers-on-left-side-in-an-array/
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
{
int[] arr = new int[] { 1, 3, 0, 2, 5 };
printArray(arr);
printArray(nearestSmallestOnLeftSideInArray(arr));
}
private static void printArray(int[] arr) {
System.
out.
println("TestSort.printArray()"); for (int i = 0; i < arr.length; i++) {
System.
out.
print(arr
[i
] + " "); }
}
private static int[] nearestSmallestOnLeftSideInArray(int[] arr) {
Stack<Integer> stack = new Stack<>();
int nearestSmallest[] = new int[arr.length];
stack.push(arr.length - 1);
for (int i = arr.length - 2; i >= 0; i--) {
if (stack.peek() != null) {
while (true) {
if (stack.isEmpty() || arr[i] > arr[stack.peek()]) {
break;
}
nearestSmallest[stack.pop()] = arr[i];
}
}
stack.push(i);
}
while (!stack.isEmpty()) {
nearestSmallest[stack.pop()] = -1;
}
return nearestSmallest;
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovL0ZpbmQgdGhlIG5lYXJlc3Qgc21hbGxlciBudW1iZXJzIG9uIGxlZnQgc2lkZSBpbiBhbiBhcnJheQovL2h0dHA6Ly93Li4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5zLm9yZy9maW5kLXRoZS1uZWFyZXN0LXNtYWxsZXItbnVtYmVycy1vbi1sZWZ0LXNpZGUtaW4tYW4tYXJyYXkvCgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCWludFtdIGFyciA9IG5ldyBpbnRbXSB7IDEsIDMsIDAsIDIsIDUgfTsKCQlwcmludEFycmF5KGFycik7CgkJU3lzdGVtLm91dC5wcmludGxuKCIiKTsKCQlwcmludEFycmF5KG5lYXJlc3RTbWFsbGVzdE9uTGVmdFNpZGVJbkFycmF5KGFycikpOwoJfQoJCglwcml2YXRlIHN0YXRpYyB2b2lkIHByaW50QXJyYXkoaW50W10gYXJyKSB7CgkJU3lzdGVtLm91dC5wcmludGxuKCIiKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oIlRlc3RTb3J0LnByaW50QXJyYXkoKSIpOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgYXJyLmxlbmd0aDsgaSsrKSB7CgkJCVN5c3RlbS5vdXQucHJpbnQoYXJyW2ldICsgIiAiKTsKCQl9Cgl9CgkKCQlwcml2YXRlIHN0YXRpYyBpbnRbXSBuZWFyZXN0U21hbGxlc3RPbkxlZnRTaWRlSW5BcnJheShpbnRbXSBhcnIpIHsKCQlTdGFjazxJbnRlZ2VyPiBzdGFjayA9IG5ldyBTdGFjazw+KCk7CgkJaW50IG5lYXJlc3RTbWFsbGVzdFtdID0gbmV3IGludFthcnIubGVuZ3RoXTsKCgkJc3RhY2sucHVzaChhcnIubGVuZ3RoIC0gMSk7CgoJCWZvciAoaW50IGkgPSBhcnIubGVuZ3RoIC0gMjsgaSA+PSAwOyBpLS0pIHsKCQkJaWYgKHN0YWNrLnBlZWsoKSAhPSBudWxsKSB7CgkJCQl3aGlsZSAodHJ1ZSkgewoJCQkJCWlmIChzdGFjay5pc0VtcHR5KCkgfHwgYXJyW2ldID4gYXJyW3N0YWNrLnBlZWsoKV0pIHsKCQkJCQkJYnJlYWs7CgkJCQkJfQoJCQkJCW5lYXJlc3RTbWFsbGVzdFtzdGFjay5wb3AoKV0gPSBhcnJbaV07CgkJCQl9CgkJCX0KCQkJc3RhY2sucHVzaChpKTsKCQl9CgoJCXdoaWxlICghc3RhY2suaXNFbXB0eSgpKSB7CgkJCW5lYXJlc3RTbWFsbGVzdFtzdGFjay5wb3AoKV0gPSAtMTsKCQl9CgoJCXJldHVybiBuZWFyZXN0U21hbGxlc3Q7Cgl9CgkKCQp9