Stacks

Question 1

Nearest smaller element on the left side

Answer 1

int[] a = {4, 6, 10, 11, 7, 8, 3, 5};
int[] ans = new int[a.length];
Arrays.fill(ans, -1);
for(int i = 0; i < a.length; i++) {
for(int j = i-1; j >=0; j–) {
if(a[j] < a[i]) {
ans[i] = a[j];
break;
}
}
}
Stack - Always access/delete the latest element.
s.push(a[0]);
for(int i = 0; i < a.length; i++) {
if(!s.isEmpty()) {
if(s.peek() > a[i]) {
while(!s.isEmpty() && s.peek() > a[i]) {
s.pop();
}
}
if(!s.isEmpty() && s.peek() < a[i]) {
ans[i] = s.peek();
}
s.push(a[i]);
}
}

			1) Push the first element to stack
			2) Iterate all the elements and check if stack top element is less than current element and update the result array
			3) Else remove the elements greater than the current element
			4) Add the top element if exists , in the result array
			5) push the current element to the stack

Question 2

Find the max histogram area