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。如何利用单调递增栈实现上述过程呢？在将数组元素压入栈时需要遵循下面的规则：

1. 如果当前栈stack为空或者当前数组的元素arr[j]>arr[stack.top()](栈顶元素)，那么直接把当前元素的位置j压入stack。
2. 如果当前栈不为空且当前数组元素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。

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

题目四

??一个n位的数，去掉其中的k位，问怎样去掉使得留下来的那个（n-k）位的数最小？
?需要注意的是，给定的整数大小可以超过long类型的范围，所以需要用字符串来表示。

解法一

思路： 现在假设有一个数，124682385， 假如k = 1，则结果为12462385,k = 2，结果为1242385……?可以知道：最优解是删除出现的第一个左边>右边的数，因为删除之后高位减小，?那全局最优解也就是这个了，因为删除S个数字就相当于执行了S次删除一个数，因为留下的数总是当前最优解

            /**
	 * 删除整数的k个数字，获得删除后的最小值
	 * 
	 * @param num 原整数
	 * @param k   删除数量
	 * 
	 */
	public static String removeKDigits(String num, int k) {

		String numNew = num;

		for (int i = 0; i < k; i++) {
			boolean hasCut = false;
			// 从左向右遍历，找到比自己右侧数字大的数字并删除
			for (int j = 0; j < numNew.length() - 1; j++) {

				if (numNew.charAt(j) > numNew.charAt(j + 1)) {
					numNew = numNew.substring(0, j) + numNew.substring(j + 1, numNew.length());
					hasCut = true;
					break;
				}
			}

			// 如果没有找到要删除的数字，则删除最后一个数字
			if (!hasCut) {
				numNew = numNew.substring(0, numNew.length() - 1);
			}

			// 清除整数左侧的数字0
			numNew = removeZero(numNew);
		}

		// 如果整数的所有数字都被删除了，直接返回0
		if (numNew.length() == 0) {
			return "0";
		}
		return numNew;

	}


	private static String removeZero(String num) {

		for (int i = 0; i < num.length() - 1; i++) {
			if (num.charAt(0) != ‘0‘) {
				break;
			}
			num = num.substring(1, num.length());
		}

		return num;

	}

        

解法二

思路：removeKDigits的优化(单调栈)
? ? ? ? ??1.每一次内层循环，都需要从头遍历所有数字
? ? ? ? ??2.subString ?方法的底层实现，涉及到了新字符串的创建，以及逐个字符的拷贝。这个方法自身的时间复杂度是O（n）??下面代码中非常巧妙地运用了栈的特性，在遍历原整数的数字时，让所有数字一个? ? ? ? ? ? 个入栈，当某个数字需要删除时，?让该数字出栈。最后，程序把栈中的元素转化为字符串结果。

            /**
	 * 删除整数的k个数字，获得删除后的最小值
	 * @param num 原整数
	 * @param k   删除数量
	 */
	public 	static 	String removeKDigits2(String num, int k) {

		// 新整数的最终长度 = 原整数长度 - k
		int newLength = num.length() - k;
		// 创建一个栈，用于接收所有的数字
		char[] stack = new char[num.length()];
		int top = 0;

		for (int i = 0; i < num.length(); ++i) {

			// 遍历当前数字
			char c = num.charAt(i);
			// 当栈顶数字大于遍历到的当前数字，栈顶数字出栈（相当于删除数字）
			while (top > 0 && stack[top - 1] > c && k > 0) {
				top -= 1;
				k -= 1;
			}
			// 遍历到的当前数字入栈
			stack[top++] = c;
		}

		// 找到栈中第一个非零数字的位置，以此构建新的整数字符串
		int offset = 0;
		while (offset < newLength && stack[offset] == ‘0‘) {
			offset++;
		}

		return offset == newLength ? "0" : new
		String(stack, offset, newLength - offset);
	}