LeetCode终极版单调栈

581. 最短无序连续子数组

581. 最短无序连续子数组

给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
你找到的子数组应是最短的，请输出它的长度。
示例 1:
输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
说明 :
输入的数组长度范围在 [1, 10,000]。
输入的数组可能包含重复元素 ，所以升序的意思是<=。

遍历

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        Deque<Integer> stack = new LinkedList<>();
        int left = nums.length, right = 0;
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peekFirst()] > nums[i]) {
                left = Math.min(left, stack.pollFirst());
            }
            stack.offerFirst(i);
        }
        stack.clear();
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peekFirst()] < nums[i]) {
                right = Math.max(right, stack.pollFirst());
            }
            stack.offerFirst(i);
        }
        return right - left > 0 ? right - left + 1 : 0;
    }
}

84. 柱状图中最大的矩形

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

示例:

输入: [2,1,5,6,2,3]
输出: 10

单调栈

class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return heights[0];
        }
        int[] newHeights = new int[len + 2];
        for (int i = 0; i < len; ++i) {
            newHeights[i + 1] = heights[i];
        }
        int maxArea = 0;
        len += 2;
        heights = newHeights;
        Deque<Integer> stack = new LinkedList<>();
        stack.addFirst(0);
        // 栈中存储数组中递增的元素下标，如果栈顶元素大于下一元素就出栈
        for (int i = 1; i < len; ++i) {
            while (heights[stack.peekFirst()] > heights[i]) {
                int height = heights[stack.removeFirst()];
                int width = i - stack.peekFirst() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.addFirst(i);
        }
        return maxArea;
    }
}

85. 最大矩形

85. 最大矩形

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例:

输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6

单调栈

详解见leetcode，可以对比leetcode 84

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int ans = 0;
        int rowLen = matrix.length;
        int columnLen = matrix[0].length;
        // dp数组存储的是长方形的高度
        int[] dp = new int[columnLen];
        for (int i = 0; i < rowLen; i++) {
            for (int j = 0; j < columnLen; j++) {
                dp[j] = matrix[i][j] == '1' ? dp[j] + 1 : 0;
            }
            ans = Math.max(ans, maxArea(dp));
        }
        return ans;
    }

    private int maxArea(int[] heights) {
        Deque<Integer> stack = new LinkedList<>();
        stack.offerFirst(-1);
        int maxarea = 0;
        for (int i = 0; i < heights.length; i++) {
            while (stack.peekFirst() != -1 && heights[stack.peekFirst()] >= heights[i]) {
                maxarea = Math.max(maxarea, heights[stack.pollFirst()] * (i - stack.peekFirst() - 1));
            }
            stack.offerFirst(i);
        }
        while (stack.peekFirst() != -1) {
            maxarea = Math.max(maxarea, heights[stack.pollFirst()] * (heights.length - stack.peekFirst() - 1));
        }
        return maxarea;
    }
}

剑指 Offer 33. 二叉搜索树的后序遍历序列

剑指 Offer 33. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

     5
    / \
   2   6
  / \
 1   3
示例 1：

输入: [1,6,3,2,5]
输出: false
示例 2：

输入: [1,3,2,6,5]
输出: true


提示：

数组长度 <= 1000

单调栈

详解见leetcode

后序遍历的倒序就是先序遍历的先访问根节点，再访问右子树，再访问左子树。

每次遍历找到root节点，如果当前结点的值小于root节点，说明就是合法的。

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        Deque<Integer> stack = new LinkedList<>();
        int root = Integer.MAX_VALUE;
        for (int i = postorder.length - 1; i >= 0; i--) {
            if (postorder[i] > root) {
                return false;
            }
            while (!stack.isEmpty() && stack.peekFirst() > postorder[i]) {
                root = stack.pollFirst();
            }
            stack.addFirst(postorder[i]);
        }
        return true;
    }
}