Leetcode P456 Java使用单调栈来解决

Leetcode P456 Java使用单调栈来解决

执行用时：21 ms, 在所有 Java 提交中击败了40.96%的用户

内存消耗：59.7 MB, 在所有 Java 提交中击败了82.52%的用户

ideas

​ 创建一个数组，用来记录从i到num.length()中最小的数，接下来在创建一个栈从后往前遍历数组，这个栈找到大于min[i]且小于nums[i]的元素。

​ 首先判断下数组长度是否小于3，如果小于是false

        if (nums.length < 3){
            return false;
        }
1
2
3

​ 创建一个数组用来记录i到num.length中最小的数，这么做的原因就是保证我们132中的其中1要保证是最小的值

//用来维护第一个数字是最小的
int[] minarr = new int[nums.length];
minarr[0] = nums[0];

for (int i = 1; i < nums.length; i++) {
    minarr[i] = Math.min(minarr[i-1],nums[i]);
}
1
2
3
4
5
6
7

接下来创建一个栈用，然后从后往前遍历去找到大于min[i]且小于nums[i]的元素。

       Stack<Integer> stack = new Stack<>();
        for (int i = nums.length-1; i >= 0 ; i--) {
     			......
        }
1
2
3
4

在循环期间一定要先筛选出num[i] > min[i]的元素，因为只有满足这个条件才能是我们想要的元素

        for (int i = nums.length-1; i >= 0 ; i--) {
            if (nums[i] > minarr[i]){
							 ...
            }
        }
1
2
3
4
5

如果满足了这个条件，如果我们的栈不为NULL，但是我们栈中的元素小于等于minarr[i]的元素，然后直接把把栈中的元素抛出，这么做就是为了保证找出132 其中的2

                //把栈里小于当前下标的最小值的全部移除
                while (!stack.isEmpty() && stack.peek() <= minarr[i]){
                    stack.pop();
                }
1
2
3
4

接下来判断我们栈中的peek()是否小于nums[i],如果小于那么我们就找到了大于min[i]且小于nums[i]的元素

if (!stack.isEmpty() && stack.peek() <nums[i]){
    return true;
}
1
2
3

如果if不合法，那么就证明，当前这个元素可能是我们想要的132中的3，所以我们把当前这个元素添加到stack中，在后续的判断是否满足132.

stack.push(nums[i]);
1

如果以上循环没有找到我们要的元素，那么直接返回false