一、題目 1、題目描述

給定 n n n 個(gè)非負(fù)整數(shù)，用來(lái)表示柱狀圖中各個(gè)柱子的高度。每個(gè)柱子彼此相鄰，且寬度為 1 。

創(chuàng)新互聯(lián)專(zhuān)注于淅川企業(yè)網(wǎng)站建設(shè),成都響應(yīng)式網(wǎng)站建設(shè)公司,商城網(wǎng)站建設(shè)。淅川網(wǎng)站建設(shè)公司,為淅川等地區(qū)提供建站服務(wù)。全流程定制制作，專(zhuān)業(yè)設(shè)計(jì)，全程項(xiàng)目跟蹤，創(chuàng)新互聯(lián)專(zhuān)業(yè)和態(tài)度為您提供的服務(wù)

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

示例1：

輸入：heights = [2,1,5,6,2,3]
輸出：10
解釋?zhuān)捍蟮木匦螢閳D中紅色區(qū)域，面積為 10

示例2：

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

2、基礎(chǔ)框架

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

3、原題鏈接

84. 柱狀圖中大的矩形

二、解題報(bào)告 1、思路分析

例子：

那么大的長(zhǎng)方形面積是如下圖中的紅色區(qū)域：

整體思路就是 必須以每個(gè)位置的直方圖作為高的長(zhǎng)方形能擴(kuò)多遠(yuǎn)，遇到相同的高度時(shí)進(jìn)行錯(cuò)化處理，最終是能計(jì)算正確的。

如何找到以每個(gè)位置的直方圖作為高的長(zhǎng)方形能擴(kuò)充的范圍呢？

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

2、時(shí)間復(fù)雜度

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

3、代碼詳解

• C++版

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

        int n = heights.size();

        int _stack[n]; //準(zhǔn)備一個(gè)棧，此處使用數(shù)組替代系統(tǒng)棧
        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]) {//棧不為空 且 棧頂元素對(duì)應(yīng)的值>=當(dāng)前元素位置對(duì)應(yīng)的值
                int cur = heights[_stack[si--]]; //獲取棧頂位置的直方圖高度
                int left = si == -1 ? -1 : _stack[si]; //找到左邊最近的比棧頂位置直方圖低的位置
                ans = max(ans, (i - left - 1) * cur); //右邊最近的比棧頂位置直方圖低的是i位置
                //所以以cur為高度的長(zhǎng)方形能擴(kuò)充的范圍就是[left + 1, i - 1],寬度為(i - left - 1)
            }
            _stack[++si] = i;
        }

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

        return ans;
    }
};

//使用系統(tǒng)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 {//使用系統(tǒng)棧
	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;
	}
	
	//使用數(shù)組替代系統(tǒng)棧
	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;
	}
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁(yè)標(biāo)題：Leetcode84.柱狀圖中最大的矩形（困難）-創(chuàng)新互聯(lián)
文章位置：http://jinyejixie.com/article38/jedsp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供動(dòng)態(tài)網(wǎng)站、網(wǎng)站營(yíng)銷(xiāo)、網(wǎng)站設(shè)計(jì)公司、軟件開(kāi)發(fā)、網(wǎng)站維護(hù)、品牌網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)