# Algorithm Pattern – Monotone Stack (LC 496 739 503)

#### Question

Monotone Stack question usually ask you to find the next greater integer in an array.

#### Approach

Maintain a monotone stack, which stores index of descending integers, and while you face an element greater than the top of stack, we could assign this element as the next greater integer.

#### Algorithm Pattern

``````Deque<Integer> stack = new ArrayDeque<>(); // our monotone stack
int[] res = new int[length]; // the result array

//go over the array
for(int i = 0; i < array.length; i++){
// if stack is empty(first one) or the current element in smaller than the top element of stack
If(stack.isEmpty() || nums[i] < nums[stack.peek()]){
stack.push(i); // insert index rather than the real value
continue;
}

// if not empty and the current element is greater than the top element
While(nums[i] > nums[stack.peek()]){
res[stack.peek()] = nums[i];
}
}
return res;``````

#### Example

##### 496. Next Greater Element I

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.
You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.
For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.
Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:

• 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
• 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
• 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
• 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
• 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

My Solution

``````class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Deque<Integer> stack = new ArrayDeque<>();
Map<Integer, Integer> map = new HashMap<>();

// go over the nums2 and get the next greater one
int[] greater = new int[nums2.length];
for(int i = 0; i < nums2.length; i++){
map.put(nums2[i], i); // store the pair of integer and index into hashmap

// only push to stack if in descending order
if(stack.isEmpty() || nums2[i] < nums2[stack.peek()]){
stack.push(i);
continue;
}
// if current one is a greater one, we update for all previous values
while(!stack.isEmpty() && nums2[i] > nums2[stack.peek()]){
greater[stack.pop()] = nums2[i];
}
// push current one into stack
stack.push(i);
}

// set the values for nums1
int[] ret = new int[nums1.length];
int index = 0;
for(int num : nums1){
int idx = map.get(num);
ret[index++] = greater[idx] == 0 ? -1 : greater[idx];
}

return ret;
}
}``````
##### 739. Daily Temperatures

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]

``````My Solution

class Solution {
public int[] dailyTemperatures(int[] temperatures) {
Deque<Integer> stack = new ArrayDeque<>(); // store index
int[] res = new int[temperatures.length];

// go over the temperatures and store the index if descending
for(int i = 0; i < temperatures.length; i++){
if(stack.isEmpty()){
stack.push(i);
continue;
}

int cur = temperatures[i];
if(cur > temperatures[stack.peek()]){
// assgin the distance to every index with a smaller value
while(!stack.isEmpty() && cur > temperatures[stack.peek()]){
res[stack.peek()] = i - stack.pop();
}
}

stack.push(i);
}

return res;
}
}``````

#### What if circular array

A simple way is to re-iterate the array to mimic the circular status.

##### 503. Next Greater Element II

Given a circular integer array nums (i.e., the next element of nums[nums.length – 1] is nums[0]), return the next greater number for every element in nums.
The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, return -1 for this number.

Example 1:
Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: The first 1’s next greater number is 2;
The number 2 can’t find next greater number.
The second 1’s next greater number needs to search circularly, which is also 2.
Example 2:
Input: nums = [1,2,3,4,3]
Output: [2,3,4,-1,4]

``````My Solution

class Solution {
public int[] nextGreaterElements(int[] nums) {
Deque<Integer> stack = new ArrayDeque<>();
int[] res = new int[nums.length];
Arrays.fill(res, -1);

for(int i = 0; i < nums.length; i++){
if(stack.isEmpty() || nums[i] < nums[stack.peek()]){
stack.push(i);
continue;
}

while(!stack.isEmpty() && nums[i] > nums[stack.peek()]){
res[stack.pop()] = nums[i];
}
stack.push(i);
}

if(stack.isEmpty()){
return res;
}

for(int i = 0; i < nums.length; i++){
while(!stack.isEmpty() && nums[i] > nums[stack.peek()]){
res[stack.pop()] = nums[i];
}
}

return res;
}
}``````