LeetCode Largest Rectangle in Histogram又一个极品程序

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.< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+CjwvcD4KPHA+CkZvciBleGFtcGxlLDxicj4KR2l2ZW4gaGVpZ2h0ID0gPGNvZGU+WzIsMSw1LDYsMiwzXTwvY29kZT4sPGJyPgpyZXR1cm4gPGNvZGU+MTA8L2NvZGU+LjwvcD4KPHA+yvTT2su8z+u63MTRo6y1q8rHs8zQ8rrcvPK1pbXEzOLEv6GjPC9wPgo8cD7T0Ly4uPbQxLXDo7o8L3A+CjxwPjEg0rLU+L6tv7zCx7n90OjSqrzHwry12tK71+61zbjftsijrLXatv7X7rXNuN+2yKOstdrI/dfutc2437bIo6zU9cO0vs3Kx8O709DP67P2wLTKx9Do0qrKudPD1bvAtLGjs9bV4tH5tcTK/b7dxNijvzwvcD4KPHA+tPCjus/CtM7T9rW9wOAmIzIwMjg0O7XEzOLEv9KqvMfXoaOs0OjSqsq508PVu8C0saO05sr9vt2hozwvcD4KPHA+MiC1scew1vnX06Os1PXDtLLFy+PKx9fps8nBy9futPPWsbe9zbzD5rv9xNijvzwvcD4KPHA+tPCjusO/uPa3vdb5vMbL49a70OjSqrzGy+PX1Ly6tcTX7rTz1rG3vc28vs2/ydLUwcujrLK70OjSqr+8wsexyNfUvLq1zbXEt73W+aOs0vLOqrHI19S8urXNtcS3vdb5ysfTybHI19S8urXNtcS3vdb5uLrU8LXEo6E8L3A+CjxwPjxicj4Ksb7M4rXEvqvSqsu8z+ujusO/uPa3vdb5trzWu9Do0qq6zdfUvLrB2r38tcS089Pa19S8urXEt73W+dfps8mxvre91vnX7rTz1rG3vc28o6zIu7rzy/nT0KOsbrj2o6zWsbe9zbyxyL3Po6zX7rTztcTWsbe9zby+zcrHtPCwuMHLoaM8YnI+CjwvcD4KPHA+PGJyPgo8L3A+CjxwPs7Sv7TBy8G9uPbQocqxo6zA48rHw7vP67W9veK+9re9t6iho8/rs/bBy7j2tv631reoo6yyu7n9yrG85NCnwsrKx08obmxnbimjrNfuu7XH6b/2u7nKx08obipuKaOsy/nS1LOsyrGhozwvcD4KPHA+w7u/tLn9wOAmIzIwMjg0O8zixL+jrNXmvvW1w8rHtvrEv9K70MK1xMzixL+jrLK7uf3V4rXAzOK1xNfu08W94qOsTyhuKcqxvOS4tNTTtsijrNKq19S8utHQvr+z9sC0o6zO0rnAvMbG8MLrysew67j2zOyyxcHLoaM8L3A+CjxwPsu8v7zV4rXAzOK1xMqxuvLX3L71tcOy7sTHw7TSu7XjteOjrNK7teO1477NxNzQtLP2TyhuKcvjt6jAtMHLo6yyu7n9vs3Kx7LuxMfDtNK7teO146OsxMfDtNK7teO149StwLTKx8jntMvE0dLU0+LUvbXEoaM8L3A+CjxwPr6vzOjX1Ly6o6zSsr6vzOi688C0yMujrLK70qrS1M6qobCy7rK7tuChsbCho6HEx9K7sr3WrtKjo6zW0LzkuPS1xNKy0O3Kx83y1cnJ7tSosKGhozwvcD4KPHA+PGJyPgo8L3A+CjxwPrLOv7zBy9K7z8JsZWV0Y29kZcnPtcSzzNDyo6zX1Ly60LTBy7j2o7o8L3A+CjxwPjwvcD4KPHByZSBjbGFzcz0="brush:java;">int largestRectangleArea(vector &h) { h.push_back(0); int n = h.size(); //初始化应该是0，不应该是INT_MIN int maxArea = 0; stack stk; for (int i = 0; i < n; ) { //注意别漏了stk.empty()这个条件 //且条件不是h[i]<=h[i+1],是入栈的的栈顶元素和当前元素对比 if (stk.empty() || h[stk.top()]<=h[i]) stk.push(i++); else { int t = stk.top(); stk.pop(); maxArea = max(maxArea, h[t]*(stk.empty() i:i-1-stk.top())); } } return maxArea; }
精典程序，让人叹服，感觉每句，每个细节都优化到极点了，不能修改了。