CCF CSP 201312-3最大的矩形

问题描述

思路

暴力法，复杂度O(n^2)

  * 遍历每个高度，以当前高度h[i]为矩形的最大高度maxh。
  * 从当前高度开始往后遍历它后面的高度h[j]，如果小于maxh,令maxh=h[j]，表示矩形最大高度变小了。
  ** 宽度为i-j+1, 计算当前矩形的面积s。
  ** 如果s大于ans，记录下最大的面积。

int boli(){
	int ans = 0;
	int n;
	int h[N];
	int maxh, s;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>h[i];
	}
	for(int i=0;i<n;i++) {
		maxh=h[i];
		for(int j=i;j<n;j++){
			if(h[j]<maxh){
				maxh=h[j];
			}
			s = (j-i+1) * maxh;
			if(s > ans) ans = s;
		}
	}
	return ans;
}

用栈维护一个递增的序列，栈中存对应高度的下标，复杂度O(n)

  * 每遍历一个元素，判断它是不是大于栈顶元素(保证序列递增)
  ** 如果是，入栈，栈仍是递增的。
  ** 如果不是，弹出栈顶的元素，并计算以该栈顶元素为最大高度时的长方形面积。
  *** 面积的长度为栈顶元素之前的一个元素到当前遍历的元素的之间的长度，i-s.top()-1表示大于等于h[tp]的个数。
  *** 边界情况(弹出栈顶后栈为空)特殊考虑，长度为i。
  ** 遍历结束后，栈中元素的最长递增子序列,继续遍历这个栈。

int func(){
	int n;
	int h[N];
	stack<int> s;  //s是一个递增序列 
	int maxs=0, tp;
	cin>>n;
	for(int i=0; i<n; i++){
		cin>>h[i];
	}
	int i=0;
	while(i < n){
		//每遍历一个元素，判断它是不是大于栈顶元素(保证序列递增) 
		if(s.empty() || h[i] > h[s.top()]) 
			s.push(i), i++;
		//如果不是，弹出栈顶的元素，并计算以该栈顶元素为最大高度时的长方形面积 
		else{  
			tp = s.top();  
			s.pop();
			if(!s.empty())
				maxs = max(maxs, (i-s.top()-1) * h[tp]);  //i-s.top()-1 表示大于等于h[tp]的个数 
			else
				maxs = max(maxs, i * h[tp]);
		}
	}
	//剩余的是最长递增子序列 
	while(!s.empty()){  
		tp = s.top();
		s.pop();
		if(!s.empty()) 
			maxs = max(maxs, (n-s.top()-1) * h[tp]);
		else 
			maxs = max(maxs, n*h[tp]);
	}
	return maxs;
}

参考：https://www.cnblogs.com/Ritchie/p/6138995.html

CCF CSP 201312-3最大的矩形

原文：https://www.cnblogs.com/monster-yher/p/13110778.html