LeetCode085最大子矩形（相关话题：单调栈）

题目描述：

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

示例:

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

解题思路：

1、计算每个行和前面所有行叠加所产生的数组里的最大子矩阵,求出最大的数组里的最大子矩阵。叠加规则为遇到1累加，遇到0重新开始计算

2、数组的最大子矩阵实际就是求以j为中心向左右寻找第一个比j柱子小的柱子，然后计算对应的矩形面积后比较大小

如何求arr[j]数组的最大矩形大小

求数组最大矩形大小，我们是利用一个单调栈来实现的。单调栈顾名思义就是栈的元素从栈底到栈顶依次是递增或递减的。利用单调递增栈我们可以求出数组中每一个元素左边离它最近比它小的位置和右边离它最近比它小的位置在哪里。例如对于数组{3,1,3,2,2}对于第一个元素左边离它最近比它小的位置为空，右边离它最近比它小的位置在哪里为1。如何利用单调递增栈实现上述过程呢？在将数组元素压入栈时需要遵循下面的规则：

如果当前栈stack为空或者当前数组的元素arr[j]>arr[stack.top()](栈顶元素)，那么直接把当前元素的位置j压入stack。如果当前栈不为空且当前数组元素arr[j]<=arr[stack.top()](栈顶元素),那么依次从stack弹出元素，并结算栈顶元素为根基，向左和向右分别可以拓展到哪里，则可以得出当前最大子矩阵的大小为多少。

结算最大矩阵大小思想如下：

如何当前遍历的元素的元素为i，当前栈顶元素元素为j,弹出栈顶元素后，新的栈顶元素为k。那么现在考虑以元素为j为根基，其向左最左能达到k+1,因为j最左最近小于j的元素应该为k,那么向右最远应该能到i-1,因为j之所以被弹出，就是因为遇到了第一个比位置j值小的位置。所以其最大子矩阵大小结算为(i-k-1)*height[j].

代码示例：

public int getMatrixMaxSum(int matrix[][]) { int arr[] = new int[matrix.length]; Integer maxSum = 0; for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[i].length; j++) { arr[j] = (matrix[i][j] > 0 ? 0 : arr[j] + 1); } maxSum = Math.max(maxSum, getArrMaxSum(arr)); } return 0; } private int getArrMaxSum(int[] arr) { // TODO Auto-generated method stub Stack<Integer> stack = new Stack(); Integer j = null; Integer k = -1; int max = 0; for (int i = 0; i < arr.length; i++) { k = stack.peek(); while (!stack.isEmpty() && arr[k] >= arr[i]) { j = stack.pop(); k = stack.peek(); max = Math.max(max, ((i - 1) - (k + 1) + 1) * arr[j]); } stack.push(i); } //i=arr.length - 1 仍然需要计算栈内剩余数据所构成的组合情况 while (!stack.isEmpty()) { j = stack.pop(); k = stack.isEmpty() ? -1 : stack.peek(); max = Math.max(max, ((arr.length - 1) - (k + 1) + 1) * arr[j]); } return max; }

变形题：

题目一

 Next Greater Number 的原始问题，这是力扣第 496 题「下一个更大元素 I」：

给你一个数组，返回一个等长的数组，对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1。

比如说，输入一个数组nums = [2,1,2,4,3]，你返回数组[4,2,4,-1,-1]。

解释：第一个 2 后面比 2 大的数是 4; 1 后面比 1 大的数是 2；第二个 2 后面比 2 大的数是 4; 4 后面没有比 4 大的数，填 -1；3 后面没有比 3 大的数，填 -1。

List<Integer> nextGreaterElement(int[] nums) { List<Integer> res =new ArrayList<Integer>(); Stack<Integer> s= new Stack(); // 倒着往栈里放 for (int i = nums.size() - 1; i >= 0; i--) { // 判定个子高矮 while (!s.empty() && s.top() <= nums[i]) { // 矮个起开，反正也被挡着了。。。 s.pop(); } // nums[i] 身后的 next great number res .add(s.empty() ? -1 : s.top()); // s.push(nums[i]); } return res; }

题目二

力扣第 1118 题「一月有多少天」：

给你一个数组T，这个数组存放的是近几天的天气气温，你返回一个等长的数组，计算：对于每一天，你还要至少等多少天才能等到一个更暖和的气温；如果等不到那一天，填 0。

比如说给你输入T = [73,74,75,71,69,76]，你返回[1,1,3,2,1,0]。

解释：第一天 73 华氏度，第二天 74 华氏度，比 73 大，所以对于第一天，只要等一天就能等到一个更暖和的气温，后面的同理。

List<Integer> dailyTemperatures(int[] T) { List<Integer> res =new ArrayList<Integer>(); // 这里放元素索引，而不是元素 Stack<Integer> s= new Stack(); /* 单调栈模板 */ for (int i = T.length - 1; i >= 0; i--) { while (!s.empty() && T[s.top()] <= T[i]) { s.pop(); } // 得到索引间距 res.add(s.empty() ? 0 : (s.top() - i)); // 将索引入栈，而不是元素 s.push(i); } return res; }

题目三

 Next Greater Number，现在假设给你的数组是个环形的，如何处理？力扣第 503 题「下一个更大元素 II」就是这个问题：

比如输入一个数组[2,1,2,4,3]，你返回数组[4,2,4,-1,4]。拥有了环形属性，最后一个元素 3 绕了一圈后找到了比自己大的元素 4。

思路：把这个双倍长度的数组构造出来，然后套用算法模板 

参考文章：

https://blog.csdn.net/u013616945/article/details/77282308

https://mp.weixin.qq.com/s/KYfjBejo84AmajnPZNs5nA