单调栈题解

单调栈结构

牛客链接

方法：单调栈

这里维护一个单调递增栈，可以找到比当前元素要小的元素。

算法
约定：当前元素 cur，栈顶元素 top，出栈的栈顶元素 tempTop

• 遍历数组
• 如果当前元素大于栈顶元素，则入栈(入栈元素索引，而不是值)
• 否则，将栈顶元素出栈，此时，离 tempTop 左边最近且值比 tempTop 小的就是当前的栈顶元素 top，离 tempTop 右边最近且值比 tempTop 小的就是当前元素 cur。 然后循环此过程，直到第二步条件满足。
• 遍历数组结束后，最后将栈内元素按上述规则输出

    private static void leftRightWay(int[] arr){
        int len = arr.length;
        int[] right = new int[len];
        int[] left = new int[len];
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < len; i++) {
            while(!stack.empty() && arr[i] < arr[stack.peek()]) {
                int tempTop = stack.pop();
                left[tempTop] = stack.empty() ? -1 : stack.peek();
                right[tempTop] = i;
            }
            stack.push(i);
        }

        while(!stack.empty()) {
            int tempTop = stack.pop();
            left[tempTop] = stack.empty() ? -1 : stack.peek();
            right[tempTop] = -1;
        }

        for(int i = 0; i < len; i++) {
            System.out.println(left[i] + " " + right[i]);
        }
    }

复杂度

• 时间复杂度：O(N)，每个元素被处理两次，其索引入栈和出栈。