LeetCode刷題：84. Largest Rectangle in Histogram

LeetCode刷題：84. Largest Rectangle in Histogram

原題連結：https://leetcode.com/problems/largest-rectangle-in-histogram/

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = 

[2,1,5,6,2,3]

.

The largest rectangle is shown in the shaded area, which has area = 

10

 unit.

Example:

Input: [2,1,5,6,2,3]

Output: 10

算法分析：

題目要求，給定n個非負整數表示的柱狀圖的高度，其中每個條的寬度為1，找出柱狀圖中最大矩形的面積。

第一種方法的外層周遊，是組合矩陣的結束位置，然後在内層逐個周遊組合矩陣的開始位置。通過對這樣一個模型的分析，對于以位置 i 結束的組合矩陣來說，它與目前位置之前的矩陣的高度有一定關系：

1. 如果 i 位置的高度大于 i-1 位置的高度，則在與這個位置之前的矩陣的組合中，不能以目前位置的高度作為組合矩陣的高度。如數組[1,2]，那麼對于位置 2 來說，這兩個位置的組合不能以 2 作為組合矩陣高度。
2. 如果 i 位置的高度不大于 i-1 位置的高度，則存在高度為目前高度的組合矩陣。如數組[2，1]，對于位置 1 ，有一種組合方法[1,1]，是以在這種情況下應該判斷一下。

另外，我們知道，對于一個高度遞增的數組來說，很容易求出其組合矩陣的最大面積，那麼是否可以将任意一個矩陣轉化為一個高度遞增的矩陣序列？如将一個數組[2,3,1,3,5]變成[1,1,1,3,5]，但是這個過程中對 2 作了改變，我們要通過一定辦法彌補這裡的改變，一種方法是，在作改變前，将其能夠組成的組合矩陣的最大面積記錄下來，完了之後便可以對其做出改變了。對于上面那個例子，實際上我們是對兩個遞增的數組求解：[2,3]和[1,1,1,3,5]，而它們之間的最大解必然與[2,3,1,3,5]的解相同。于是，将一個不規則數組轉化為若幹有序數組，再進行求解，便是本方法的思想。

下面是利用棧的一種實作，利用棧的話不需要對原資料進行修改，而是直接将原數組截取成多個有序數組，通過儲存索引值确定目前的組合矩陣的寬度：

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

完整的代碼如下：

package com.bean.algorithmexec;

import java.util.Stack;

public class LargestRectangleInHistogram2 {

	public static int largestRectangleArea(int[] heights) {
	    Stack<Integer> stack = new Stack<Integer>();
	    int n = heights.length;
	    int max = 0;
	    for (int i = 0; i <= n; i++) {
	        while (!stack.empty() && (i >= n || heights[stack.peek()] > heights[i])) {
	            int top = stack.pop();
	            int h = heights[top];
	            int w = stack.empty() ? i : (i-stack.peek()-1);
	            max = Math.max(max, h*w);
	        }
	        stack.push(i);
	    }
	    return max;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] demo=new int[] {2,1,5,6,2,3};
		int result = largestRectangleArea(demo);
		System.out.println("result = "+result);
		//運作結果 10
	}

}
           

輸出結果：

result = 10

另外一種解法，采用分治算法的思想

// 思路：對于每一段區間，都存在一個最小值
	// 對于最小值，無非就是三種可能：
	// 1：要麼整段面積最大，2、3：要麼最小值左邊或者最小值右邊（均不包含最小值）的面積最大，采用分治法遞歸解決；
	// 遇到有序排列的區間，采用遞歸會降低效率，于是隻要單獨計算并且比較就可以
	public static int largestRectangleArea(int[] heights) {
		return largestRect(heights, 0, heights.length - 1);
	}

	private static int largestRect(int[] heights, int start, int end) {
		if (start > end)
			return 0;
		if (start == end)
			return heights[start];
		int minIndex = start;
		// 使用是否有序排列的變量可以顯著提高效率
		// 這裡可以檢測雙向（變大或者變小的順序）
		int inc = 0, dec = 0;
		for (int i = start + 1; i <= end; i++) {
			if (heights[i] < heights[minIndex])
				minIndex = i;
			if (heights[i] > heights[i - 1])
				inc++; // 升序
			else if (heights[i] < heights[i - 1])
				dec--; // 降序
		}
		int res = 0;
		// 升序
		if (dec == 0) {
			for (int i = start; i <= end; i++)
				res = Math.max(res, heights[i] * (end - i + 1));
		} // 降序
		else if (inc == 0) {
			for (int i = start; i <= end; i++)
				res = Math.max(res, heights[i] * (i - start + 1));
		} // 無序
		else {
			res = Math.max(Math.max(largestRect(heights, minIndex + 1, end), largestRect(heights, start, minIndex - 1)),
					heights[minIndex] * (end - start + 1));
		}
		return res;
	}
           

效果相同。