How to use monotonic stack in Java

1. The next bigger element

Problem description

Detailed explanation of ideas

For this question, choose a more violent solution .

We first initialize a res array with the same length as nums to store the results. We traverse to take out the values ​​​​in nums and search in nums2 until we find nums2[j] == nums[i]. We then Traverse from j in nums2 to find an array larger than nums[i] and return it. If it cannot find it, it returns -1.

Code and results

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] res = new int[m];
        for (int i = 0; i < m; ++i) {
            int j = 0;
            while (j < n && nums2[j] != nums1[i]) {
                ++j;
            }
            int k = j + 1;
            while (k < n && nums2[k] < nums2[j]) {
                ++k;
            }
            res[i] = k < n ? nums2[k] : -1;
        }
        return res;
    }
}

2. Daily temperature

Question description

Detailed explanation of ideas

This question also uses a relatively violent method. Same as the previous question.

Double loop, obviously this method has higher time complexity. A method with lower time complexity is also provided here.

Monotone stack

What we maintain is a gap array, which is the result array. First create a stack and determine whether the stack is empty. If it is empty, push it directly to the stack. If it is not empty, compare it. The difference between the top element of the stack and the current element. If the current element is greater than the current element, the difference is put into the corresponding result array and the top element of the stack is popped off the stack. If the current element is smaller than the result array, it is pushed onto the stack.

Here is a link to animation, it’s a good idea to learn monotonic stack in animation.

Code and results

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        for(int i = 0 ; i < temperatures.length ; i++){
            int res = 0;
            for(int j = i+1 ; j < temperatures.length; j++){
                res++;
                if(temperatures[j] > temperatures[i]){
                    answer[i] = res;
                    break;
                } 
            }
        }
        return answer;
    }
}

3. The next larger element II

Title description

Detailed explanation of the idea

The idea of ​​​​this question is the monotonic stack. Question 1 is a brute force solution. This question requires the use of a monotonic stack.

The principle is the same as the method in the second question, just pay attention to the loop. Go directly to the code. If you are not familiar with it, you can watch the video of the second question and then see this.

Code and results

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ret = new int[n];
        Arrays.fill(ret, -1);
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < n * 2 - 1; i++) {//最多循环一次，只需要2*n-1就够用了
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
                ret[stack.pop()] = nums[i % n];
            }
            stack.push(i % n);//利用取模来进行循环也是一种常用的方法
        }
        return ret;
    }
}

The above is the detailed content of How to use monotonic stack in Java. For more information, please follow other related articles on the PHP Chinese website!