一、題目 1、題目描述

給定 n n n 個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。

創新互聯專注于淅川企業網站建設,成都響應式網站建設公司,商城網站建設。淅川網站建設公司,為淅川等地區提供建站服務。全流程定制制作，專業設計，全程項目跟蹤，創新互聯專業和態度為您提供的服務

求在該柱狀圖中，能夠勾勒出來的矩形的大面積。

示例1：

輸入：heights = [2,1,5,6,2,3]
輸出：10
解釋：大的矩形為圖中紅色區域，面積為 10

示例2：

輸入： heights = [2,4]
輸出： 4

2、基礎框架

class Solution {public:
    int largestRectangleArea(vector& heights) {}
};

3、原題鏈接

84. 柱狀圖中大的矩形

二、解題報告 1、思路分析

例子：

那么大的長方形面積是如下圖中的紅色區域：

整體思路就是 必須以每個位置的直方圖作為高的長方形能擴多遠，遇到相同的高度時進行錯化處理，最終是能計算正確的。

如何找到以每個位置的直方圖作為高的長方形能擴充的范圍呢？

找到每個位置左右最近的比它矮的直方圖，除了這兩個位置不能到達，其他位置就是它所能擴充的范圍。

2、時間復雜度

O ( n ) O(n) O(n)

3、代碼詳解

• C++版

//不使用系統stack的解法
class Solution {public:
    int largestRectangleArea(vector& heights) {if (heights.size() == 0) return 0;

        int n = heights.size();

        int _stack[n]; //準備一個棧，此處使用數組替代系統棧
        memset(_stack, 0, sizeof(_stack));

        int si = -1;

        int ans = 0;

        for (int i = 0; i< n; i++) {while (si != -1 && heights[_stack[si]] >= heights[i]) {//棧不為空 且 棧頂元素對應的值>=當前元素位置對應的值
                int cur = heights[_stack[si--]]; //獲取棧頂位置的直方圖高度
                int left = si == -1 ? -1 : _stack[si]; //找到左邊最近的比棧頂位置直方圖低的位置
                ans = max(ans, (i - left - 1) * cur); //右邊最近的比棧頂位置直方圖低的是i位置
                //所以以cur為高度的長方形能擴充的范圍就是[left + 1, i - 1],寬度為(i - left - 1)
            }
            _stack[++si] = i;
        }

        while (si != -1) {//遍歷完數組后，棧中還有數據，則單獨結算
            int cur = heights[_stack[si--]];
            int left = si == -1 ? -1 : _stack[si];
            ans = max(ans, (n - left - 1) * cur);
        }

        return ans;
    }
};

//使用系統stack的解法
class Solution {public:
    int largestRectangleArea(vector& heights) {if (heights.size() == 0) return 0;

        stacksta;
        int area = 0;
        for (int i = 0; i< heights.size(); i++) {while (!sta.empty() && heights[sta.top()] >= heights[i]) {int j = sta.top();
                sta.pop();
                int k = sta.empty() ? -1 : sta.top();
                area = max(area, (i - k - 1) * heights[j]);
            }
            sta.push(i);
        }

        while (!sta.empty()) {int j = sta.top();
            sta.pop();
            int k = sta.empty() ? -1 : sta.top();
            int curArea = (heights.size() - k - 1) * heights[j];
            area = max(area, curArea);
        }
        return area;
    }
};

• Java 版

public class LargestRectangleInHistogram {//使用系統棧
	public static int largestRectangleArea1(int[] height) {if (height == null || height.length == 0) {	return 0;
		}
		int maxArea = 0;
		Stackstack = new Stack();
		for (int i = 0; i< height.length; i++) {	while (!stack.isEmpty() && height[i]<= height[stack.peek()]) {		int j = stack.pop();
				int k = stack.isEmpty() ? -1 : stack.peek();
				int curArea = (i - k - 1) * height[j];
				maxArea = Math.max(maxArea, curArea);
			}
			stack.push(i);
		}
		while (!stack.isEmpty()) {	int j = stack.pop();
			int k = stack.isEmpty() ? -1 : stack.peek();
			int curArea = (height.length - k - 1) * height[j];
			maxArea = Math.max(maxArea, curArea);
		}
		return maxArea;
	}
	
	//使用數組替代系統棧
	public static int largestRectangleArea2(int[] height) {if (height == null || height.length == 0) {	return 0;
		}
		int N = height.length;
		int[] stack = new int[N];
		int si = -1;
		int maxArea = 0;
		for (int i = 0; i< height.length; i++) {	while (si != -1 && height[i]<= height[stack[si]]) {		int j = stack[si--];
				int k = si == -1 ? -1 : stack[si];
				int curArea = (i - k - 1) * height[j];
				maxArea = Math.max(maxArea, curArea);
			}
			stack[++si] = i;
		}
		while (si != -1) {	int j = stack[si--];
			int k = si == -1 ? -1 : stack[si];
			int curArea = (height.length - k - 1) * height[j];
			maxArea = Math.max(maxArea, curArea);
		}
		return maxArea;
	}
}

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

網頁標題：Leetcode84.柱狀圖中最大的矩形（困難）-創新互聯
文章位置：http://vcdvsql.cn/article38/jedsp.html

成都網站建設公司_創新互聯，為您提供動態網站、網站營銷、網站設計公司、軟件開發、網站維護、品牌網站建設

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯