ブラシアルゴリズム[タイトル] leetcodeヒストグラムで最大の長方形
Brush Algorithm Leetcode Largest Rectangle Histogram
与えられた n 各バーの幅が1であるヒストグラムのバーの高さを表す非負の整数は、ヒストグラムで最大の長方形の領域を見つけます。
上記は、高さ= [2,1,5,6,2,3]の場合、各バーの幅が1であるヒストグラムです。
最大の長方形は、面積= 10unitの影付きの領域に表示されます。
例えば、
与えられた高さ= [2,1,5,6,2,3]、
return10
ノートブックでの彼らの理解、最初にコードを貼り付けます
int largestRectangleArea(vector &height) { if (height.empty()) return 0 int maxArea(0) stack st int i(0) int len = height.size() while (i=height[st.top()]) { st.push(i) ++i } else { int ntop = height[st.top()] st.pop() int Area = ntop*(st.empty() ? i : (i - st.top() - 1)) maxArea = max(Area, maxArea) } } while (!st.empty()) { int ntop = height[st.top()] st.pop() int Area = ntop*(st.empty() ? i : (i - st.top() - 1)) maxArea = max(Area, maxArea) } return maxArea }