可修改不可增删式线段树（类树状数组）：黄色节点可要可不要。“按位”加法式查询。
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.
For example,
Given height = [2,1,5,6,2,3],
return 10.
最佳方法 线段树
写起来容易，但优化比较难
class Solution {
public:
int tree[100000];
int get(int l, int r, int idx, int s, int t){
if(s<=l && t>=r) return tree[idx];
int mid=(l+r)/2;
if(mid>=s && mid<t)
return min(get(l, mid, idx*2+1, s, mid),
get(mid+1, r, idx*2+2, mid+1, t));
if(mid<s) return get(mid+1, r, idx*2+2, s, t);
if(mid>=t) return get(l, mid, idx*2+1, s, t);
}
int init(int l, int r, int idx, vector<int>& a){
if(l==r) return tree[idx] = a[l];
int mid = (l+r)/2;
return tree[idx] = min(init(l, mid, idx*2+1, a),
init(mid+1, r, idx*2+2, a));
}
int largestRectangleArea(vector<int> &height) {
int n =height.size();
if(n==0) return 0;///@error
init(0, n-1, 0, height);
vector<int> l, r;
for(int i=0; i<n; i++){
if(i==0 || height[i]>height[i-1]) l.push_back(i);
}
for(int j=n-1; j>=0; j--){
if(j==n-1 || height[j]>height[j+1]) r.push_back(j);
}
int mn = 0;
for(int i=0; i<l.size(); i++){
int li = l[i];
for(int j=0; j<r.size(); j++){
int lj= r[j];
if(li>lj) break;
mn = max(mn, get(0, n-1, 0, li, lj)*(lj-li+1));
}
}
return mn;
}
};
方法一 树状数组
如下，可修改不可增删式线段树（树状数组）。存储空间0(n)，更新节点代价0(lgn)
写起来比较麻烦，不容易调试，不推荐
方法二 次方数组
arr[n][k],保存[n,n+(2^k))区间。存储空间0(n*lgn)，不可增删，更新节点代价E(2*2^k),k=0~lgn. 即O（n）
写起来比较容易，注意防越界
方法三：三维dp
递推方程： maxRect[i][j]=E{ minHCnt[k...j]*(j+1-k) , max }. k=0~j. 注意剪枝。 效率o(n^3)
太慢
class Solution {
public:
#define MAXN 0x7fffffff
////线段树
struct tree{
vector<vector<int> > arr;
int n;
void init(const vector<int> &s){
n=s.size();
int step=1;
for(int i=0;i<32;i++,step<<=1){
int j=0,m=0;
if(j+step>n) break; //[0,n) don't cover [j,j+step)
arr.push_back(vector<int>());
while(j+step<=n){
int t;
if(i>0) t=min(arr[i-1][m*2+1],arr[i-1][m*2]);//[j,j+step)<=[j,j+step/2),[j+step/2,j+step)
else t=s[j];
arr[i].push_back(t);
m++,j+=step;
}
}
}
int drillLeft(int l,int mid){//[l,mid),l=xxx0yyy,mid=xxx1000
int m=MAXN;
int i,step;
//bit loop
for(i=0,step=1;i<32;i++,step<<=1){
if(l==mid) break;
if((l^mid)&step){/////@@@error l&step should be (l^mid)&step, which mean:l and mid is different at step bit, l should add 1 at this bit
m=min(m,arr[i][l>>i]);
l+=step;//l+step, set step bit ///@@@error: fault l+=step as l^=step, +/- has bit-in while ^/| don't
}
}
return m;
}
int drillRight(int mid,int r){//[mid,r),mid=xxx1000,r=xxx1zzz
int m=MAXN;
int step,i;
//bit loop
for(i=0,step=1;i<32;i++,step<<=1){
if(r==mid) break;
if(r&step){
r^=step;//r-step, clear step bit ///@@@error: r should first be smaller, than calc arr[i][r>>i]
m=min(m,arr[i][r>>i]);
}
}
return m;
}
int get(int l,int r){
int hOne=l^r;//xxx0yyy^xxx1zzz=0001uuu
int step=1;
while(hOne>step) //0001uuu=>0001000
hOne&=(~step),step<<=1;
int mid=(r&~(hOne-1));//xxx1zzz & 1111000 = xxx1000 = mid ///@@@@error: r | 1111000 , | should be &
assert(mid>=l&&r>=mid);
return min(drillLeft(l,mid),drillRight(mid,r));
}
};
int largestRectangleArea(vector<int> &height) {
int n=height.size();
if(n<1) return 0;
tree t; t.init(height);
vector<int> a,b;
for(int i=0;i<n;i++){
if(i==0||height[i]>height[i-1]) a.push_back(i);
}for(int i=0;i<n;i++){
if(i==n-1||height[i]>height[i+1]) b.push_back(i);
}
int m=0;
for(int i=0;i<a.size();i++){
int li=a[i];
vector<int>::iterator it=lower_bound(b.begin(),b.end(),li);////@@error:lower_bound mistake as lowerbound
while(it!=b.end()){
int ri=*it++;
int mHeight=t.get(li,ri+1);/////@@@@error: here not i, but li. idx_Array_Idx_Fault
m=max(m,mHeight*(ri+1-li));////@@@error: min should be max. logic_neglect_error //@@@@error: here not i, but li. idx_Array_Idx_Fault
}
}
return m;
}
};
点评：
树状数组的难点在于
1 构造时 step和下标变化。
2 查询时：
bit 运算： l,mid,r的变换;
bit loop: l趋向于mid（+和|混淆，loop中执行更新的condition，更新后r再增大) ; r趋向于mid ( 更新前r先减小）
次方数组：
class Solution {
public:
int getMin(vector<vector<int> >&mv,int l,int n){//次方数组查询
int m=0;int t=-1;
//calculate min value of [l,l+n)
while(n>0){//n shift right, and & with the lowest bit(0x1)
if(n&0x1) {
t=(t==-1?mv[l][m]:std::min(t,mv[l][m]));
l+=(1<<m);
}
n>>=1;m++;
}
return t;
}
int largestRectangleArea(vector<int> &height) {
vector<int> lI,rI;int N=height.size();
int M=0;
while(N>0){ M++;N>>=1;} //M is the bit count of N
//@@error: you pollute a variable in a temporary use
//but u forget to resume the variable N
N=height.size();
#define rep(i,n) for(int i=0;i<(int)n;i++)
rep(i,N)
if(i==N-1||height[i]>height[i+1])
rI.push_back(i);
rep(i,N)
if(i==0||height[i]>height[i-1])
lI.push_back(i);
//mv[j][i] store the min value of [j,j+(1<<i))
vector<vector<int> > mv(N,vector<int>(M,-1));//次方数组
rep(j,N) mv[j][0]=height[j];
for(int i=1;i<M;i++){ //[i,i+k), k<=(1<<(M-1))+...(1<<0)
//NOTICE: pace
int pace=(1<<(i-1));
rep(j,N){
if(j+pace>=N) mv[j][i]=mv[j][i-1];
else mv[j][i]=std::min(mv[j][i-1],mv[j+pace][i-1]);
}
}
int area=0;
// enumerate every [l,r=*it]
rep(i,lI.size()){
int l=lI[i];
vector<int>::iterator it=lower_bound(rI.begin(),rI.end(),l);
while(it!=rI.end()){
area=std::max(getMin(mv,l,*it-l+1)*(*it-l+1),area);
it++;
}
}
return area;
}
};