之前切了道求解最大正方形的题，题解猛戳 。这道题 题意与之类似，但是解法完全不一样。

先来看这道题 ，如果暴力求解，可以枚举每个点为最小值，向两边扩展，复杂度 O(n^2)。我们可以维护一个栈，从而将复杂度降低到 O(n)，这个栈的思维非常巧妙，参考了 ，我是完全想不出来（或者说忘记了）。具体代码可以猛戳 。

2016-08-07 补：stack 数组维护的是一个单调递增的数组，这貌似就是传说中的单调队列吧，后知后觉的我 ...

/** * @param {number[]} heights * @return {number} */var largestRectangleArea = function(heights) {  heights.push(0);  var maxn = 0;  var stack = [];  for (var i = 0, len = heights.length; i < len; i++) {    while (stack.length && heights[i] < heights[stack[stack.length - 1]]) {      var top = stack.pop();      var nextTop = stack.length === 0 ? -1 : stack[stack.length - 1];      maxn = Math.max((i - nextTop - 1) * heights[top], maxn);    }        stack.push(i);  }  return maxn;};

有了这个作为基础，求解最大矩形也就不难了。可以一层层向下走，维护一个数组，每次去求解当时的最值即可。代码如下。

/** * @param {number[]} heights * @return {number} */var largestRectangleArea = function(heights) {  heights.push(0);  var maxn = 0;  var stack = [];  for (var i = 0, len = heights.length; i < len; i++) {    while (stack.length && heights[i] < heights[stack[stack.length - 1]]) {      var top = stack.pop();      var nextTop = stack.length === 0 ? -1 : stack[stack.length - 1];      maxn = Math.max((i - nextTop - 1) * heights[top], maxn);    }    stack.push(i);  }  return maxn;};/** * @param {character[][]} matrix * @return {number} */var maximalRectangle = function(matrix) {  if (!matrix.length)    return 0;  var n = matrix.length    , m = matrix[0].length;  var heights = [];  for (var i = 0; i < m; i++)    heights[i] = 0;  var ans = 0;  for (var i = 0; i < n; i++) {    for (var j = 0; j < m; j++) {      if (matrix[i][j] === '1')         heights[j]++;      else         heights[j] = 0;    }    ans = Math.max(ans, largestRectangleArea(heights));  }  return ans;};

说实话这道题的解法没有认真想（算是抄的吧，这完全不符合我的个性）。最近有点浮躁，也有点烦躁，相信一切都是瞬息，一切都将会过去。

暂时先把 leetcode 放一放吧。

睡觉，身累心累啊。