单调栈

栈如其名，栈内元素保持递增/递减的顺序。

想找"从当前元素向某一方向的第一个(大于/小于)自己的元素"，就要靠单调栈来维护单调性。

曾经有个人告诉我，只有Google可能会面单调栈这么难的问题，希望他别骗我。

84. Largest Rectangle in Histogram

这个题不能用动态规划。

分析一下，这道题无非是找最大面积的左边界和右边界，然后找到两个边界中最矮的那个直方（那根木头），得出面积。（so-called 木桶原理）所以这个地方实际上就是一个被展开的木桶，每次枚举一个起点一个终点，想象成一个木桶，那么盛水的面积取决于起点到终点间最矮的那根木头。所以这道题最暴力的解法的时间复杂度是O(n^2)，枚举一个起点，一个终点，再算面积，这是两个for loop。

如果一个题能够在最暴力的解法中做到多项式级别（n^2, n^3, n^4, ...）（即P问题），那么这个题是不能用动态规划的。因为动态规划擅长的是将2^n, n^n, n!等时间复杂度级别的转为多项式的解法，而不是优化多项式级别的题。

所以这个题不能用动态规划。

回到暴力解法的分析上来，其实是暴力求解的过程中，我们做了很多无用功，比如说[2,1,5,6,2,3]这里面，枚举1为起点的for loop是没有意义的，因为1左边的高度为2的直方比1高，所以无论1有多大的面积，左边的2一定可以再加上自身的面积，从而大于1的loop中所有的可能面积。

继续分析

如果要优化n^2的解法，那么有几种可能，nlogn，logn，n。首先，nlogn一般是涉及排序的题目，这个题很明显不能排序，位置关系是这题的关键。logn一般与二分法或者树结构有关，和这题也没明显联系。

那就只剩下O(n)的方案可以试一试了。

核心点：最矮的木头

for每一块木头，以当前木头为最矮的木头，向左右去找，左边和右边第一个比它矮的木头。

所以引出了单调栈：

我们定义这样一个递增的单调栈，一组数，比如[2,1,5,6,2,3]，将所有元素一个个的push到单调栈中，如果当前栈顶的数比要push的数大，就先pop掉这个大数，一直pop到栈为空或者栈顶的数小于当前要push的数，这时再push，每一个元素都这样操作。

那么当pop的时候，我们就知道 右边第一个比它小的数 和 左边第一个比它小的数了。

举个栗子：

按照递增单调栈的规则push[2,1,5,6,2,3]，栈的变化：

[2] push 2

[ ] pop -> 2

[1] push 1

[1, 5] push 5

[1, 5, 6] push 6

[1, 5] pop -> 6

[1] pop -> 5

[1, 2] push 2

[1, 2, 3] push 3

最后得到的栈：[1,2,3]

那么对于原数组每一个数而言：它 进栈时左边的数 就是 它左边第一个比它小的数。因为比它大的数都被pop出去了。

2：进栈时左边没有数

1：进栈时左边没有数

5：进栈时左边为1

6：进栈时左边为5

2：进栈时左边为1

3：进栈时左边为2

而当某个数被pop掉的时候，我们可以同时知道，栈顶是左边第一个比他小的数，当时要进栈的数是右边第一个比它小的数。

6是在2进栈时被pop出去的，2就是6右边第一个比它小的数。

而6被pop出去的时候，栈顶为5，5就是6左边第一个比它小的数。

那么，对于2，5，6而言，这三个数已经被pop出去了，我们现在知道他们的左右两边第一个小的数都是谁了，对于还在stack内的1，2，3，我们一个个的pop他们（通过往栈内加-1，因为有的木头可能高度为零），在pop的时候，我们自然就知道他们的左右第一小是谁了。这样在stack为空后，我们得到了所有的数的左右第一小。

如果等于怎么办？

如果相等的时候，我们也要把相等的数pop出去，因为左右比它小的数是要严格小于的，只有严格小于才能保证我们的阴影部分无法向左右继续延伸。

  • curt < heights[stack.peek()]
  • curt < = heights[stack.peek()]

这两种判断都是对的，乍一看好像很神奇，实际上< =的是错误的，最后结果正确是因为如果有两个相同的高度相邻，比如1，2，2，1，那么第一个2的右边第一小其实是错的，它变成了2而不是1，但第二个2的面积计算是对的，我们只要算出最大的就行，不需要所有的面积计算都是对的。

时间复杂度

每个数都只会进出stack一次，所以时间复杂度是O(n)

注意我们在此题的单调栈中放入的是数组的下标，因为要计算面积时需要宽度，没有下标就不知道宽度。

public class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) return 0;71

        Stack<Integer> stack = new Stack<>();
        int max = 0;
        for (int i = 0; i <= heights.length; ++i) {
            int curt = (i == heights.length) ? -1 : heights[i];
            while (!stack.isEmpty() && curt < heights[stack.peek()]) {
                int h = heights[stack.pop()];
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                max = Math.max(max, h * w);
            }
            stack.push(i);
        }
        return max;
    }
}

496. Next Greater Element I

这道题和上面思路一样，用递减栈就行了，加上HashMap保存。唯一担心的是用Integer.MAX_VALUE pop其它数的时候有阴险的testcase坑我，后来发现leetcode还没那么无耻。如果改成Long.MAX_VALUE就万无一失了，但是那样int数组还得改成long数组，太麻烦了。

06/20 更新：根本没必要把那些剩下的数pop出来，不用MAX_VALUE。判断在不在map里面就行。

public class Solution {
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
        if (nums == null || findNums == null) return new int[0];
        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < nums.length; ++i) {
            int curt = nums[i];

            while (!stack.isEmpty() && curt > stack.peek()) {
                map.put(stack.pop(), curt);
            }
            stack.push(curt);
        }
        int[] result = new int[findNums.length];
        for (int i = 0; i < findNums.length; ++i) {
            int curt = findNums[i];
            if (map.containsKey(curt)) {
                result[i] = map.get(curt);
            } else result[i] = -1;
        }
        return result;
    }
}

503. Next Greater Element II

我自己的理解是遍历两遍，下标取模，因为只有一个数组所以没必要hashmap，把result初始化为-1，这样省去了最后加MAX_VALUE pop前面数的步骤，因为我们遍历两遍，前面的数肯定会被pop掉。然后稀里糊涂随便一写一次就AC了，自己都吓着了。

public class Solution {
    public int[] nextGreaterElements(int[] nums) {
        if (nums == null || nums.length == 0) return new int[0];
        int[] result = new int[nums.length];
        for (int i = 0; i < result.length; ++i) {
            result[i] = -1;
        }
        Stack<Integer> stack = new Stack<>();

        for (int j = 0; j <= nums.length * 2; ++j) {
            int i = j % nums.length;
            int curt = nums[i];

            while (!stack.isEmpty() && curt > nums[stack.peek()]) {

                result[stack.pop()] = curt;
            }
            stack.push(i);
        }
        return result;
    }
}

42. Trapping Rain Water

又是递减栈的应用，注意stack为空的时候break就行，不用MAX_VALUE pop前面，因为到最后没trap的water不需要计算了。又是一次AC。

06/16更新：注意中间是while循环，所以递减栈连续遇到相等的数也没事，我们可以一直pop到最后，横坐标 i 会记录下来计算宽度。

可以说这个是递减栈运用的模板，好好背诵。

if (stack.isEmpty()) break; 这句话很重要。

public class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) return 0;
        Stack<Integer> stack = new Stack<>();
        int result = 0;

        for (int i = 0; i < height.length; ++i) {
            int curt = height[i];

            while (!stack.isEmpty() && curt > height[stack.peek()]) {
                int mid = height[stack.pop()];
                if (stack.isEmpty()) break;
                int left = height[stack.peek()];
                int h = Math.min(left, curt) - mid;
                int w = i - stack.peek() - 1;
                result += h * w;
            }
            stack.push(i);
        }
        return result;
    }
}

85. Maximal Rectangle

85紧接84。

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length < 1) return 0;
        int n = matrix.length;
        if (n == 0) return 0;
        int m = matrix[0].length;
        if (m == 0) return 0;
        int[][] height = new int[n][m];

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (i == 0)
                    height[i][j] = ((matrix[i][j] == '1') ? 1 : 0);
                else
                    height[i][j] += ((matrix[i][j] == '1') ? height[i-1][j] + 1 : 0);
            }
        }

        int answer = 0;
        for (int i = 0; i < n; ++i) {
            Stack<Integer> S = new Stack<Integer>();  
            for (int j = 0; j < m; j++) {
                while (!S.empty() && height[i][j] < height[i][S.peek()]) {
                    int pos = S.peek();
                    S.pop();
                    answer = Math.max(answer, height[i][pos]*(S.empty()? j : j-S.peek()-1));
                }
                S.push(j);
            }
            while (!S.empty()) {
                int pos = S.peek();
                S.pop();
                answer = Math.max(answer, height[i][pos]*(S.empty()? m : m-S.peek()-1));
            }
        }
        return answer;
    }
}

Max Tree

public class Solution {
  /**
   * @param A
   *            : Given an integer array with no duplicates.
   * @return: The root of max tree.
   */
  public static TreeNode maxTree(int[] A) {
    // write your code here
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode root = null;
    for (int i = 0; i <= A.length; i++) {
      TreeNode right = i == A.length ? new TreeNode(Integer.MAX_VALUE)
          : new TreeNode(A[i]);
      while (!stack.isEmpty()) {
        if (right.val > stack.peek().val) {
          TreeNode nodeNow = stack.pop();
          if (stack.isEmpty()) {
            right.left = nodeNow;
          } else {
            TreeNode left = stack.peek();
            if (left.val > right.val) {
              right.left = nodeNow;
            } else {
              left.right = nodeNow;
            }
          }
        } else
          break;
      }
      stack.push(right);
    }
    return stack.peek().left;
  }
}
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param A: Given an integer array with no duplicates.
     * @return: The root of max tree.
     */
    public TreeNode maxTree(int[] A) {
        // write your code here
        int len = A.length;
        TreeNode[] stk = new TreeNode[len];
        for (int i = 0; i < len; ++i)
            stk[i] = new TreeNode(0);
        int cnt = 0;
        for (int i = 0; i < len; ++i) {
            TreeNode tmp = new TreeNode(A[i]);
            while (cnt > 0 && A[i] > stk[cnt-1].val) {
                tmp.left = stk[cnt-1];
                cnt --;
            }
            if (cnt > 0)
                stk[cnt - 1].right = tmp;
            stk[cnt++] = tmp;
        }
        return stk[0];
    }
}

results matching ""

    No results matching ""