//暴力 枚举宽  超时
/*
如果我们枚举「宽」，我们可以使用两重循环枚举矩形的左右边界以固定宽度 w，
此时矩形的高度 h，就是所有包含在内的柱子的「最小高度」，对应的面积为 w * h。
*/
class Solution1 {
public:
	int largestRectangleArea(vector<int>& heights) {
		int len = heights.size();
		int ans = 0;
		int minHeight;
		for(int i = 0;i<len;++i) {//枚举左边界
			minHeight = INT_MAX;
			for(int j = i;j<len;++j) {//枚举右边界
				minHeight = min(minHeight,heights[j]);
				ans = max(ans,(j-i+1)*minHeight);
			}
		}
		return ans;
	}


};

//暴力 枚举高 超时
/*
如果我们枚举「高」，我们可以使用一重循环枚举某一根柱子，将其固定为矩形的高度 h。
随后我们从这跟柱子开始向两侧延伸，直到遇到高度小于 h 的柱子，就确定了矩形的左右边界。
如果左右边界之间的宽度为 w，那么对应的面积为 w * h。

*/
class Solution2 {
public:
	int largestRectangleArea(vector<int>& heights) {
		int len = heights.size();
		int ans = 0;
		for(int mid = 0;mid<len;++mid) {
			int height = heights[mid];//当前柱子的高度
			int left = mid,right = mid;//初始化左右边界都为当前柱子的坐标
			//确定当前柱子的左右边界
			while(left-1>=0&&heights[left-1]>height) {
				left--;
			}
			while(right+1<len&&heights[right+1]>height) {
				right++;
			}
			ans = max(ans,(right-left+1)*height);
		}
		return ans;
	}
};


/*
链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/zhu-zhuang-tu-zhong-zui-da-de-ju-xing-by-leetcode-/
*/

/*
找到左右两侧最近的高度小于 h 的柱子
即找一根柱子的左(右)侧且最近的小于其高度的柱子
*/

//方法三 单调栈
class Solution {
public:
	int largestRectangleArea(vector<int>& heights) {
		int n = heights.size();
		vector<int> left(n),right(n);//存放的是该柱子左侧(右侧)最近的小于其高度的柱子的编号

		stack<int> mono_stack;//单调栈 monotonic stack
		//找左侧最近的小于其高度的柱子
		for(int i = 0;i<n;++i) {
			while(!mono_stack.empty()&&heights[mono_stack.top()]>=heights[i]) {
				//把大于等于当前柱子的柱子出栈
				mono_stack.pop();

			}
			//如果当前栈为空说明左侧没有比当前柱子低的柱子，设置哨兵 赋值为-1 虚拟一根无限低的柱子
			//否则当前栈顶元素即为当前柱子左侧最近的小于其高度的柱子，将其编号储存在数组中
			left[i] = (mono_stack.empty() ? -1 : mono_stack.top());
			mono_stack.push(i);//将当前柱子对应的编号压入栈中
		}

		mono_stack = stack<int>();//清空一个栈 或者 stack<int>().swap(mono_stack);
		//找右侧
		for(int i = n-1;i>=0;--i) {
			while(!mono_stack.empty()&&heights[mono_stack.top()]>=heights[i]) {
				mono_stack.pop();
			}
			//这里同样设置哨兵 赋值为n
			//如果某个柱子左侧没有比他低的，右侧也没有比他低的，说明宽度就是整个heights长度，高为本柱子高
			//矩形面积为 (n - (-1) - 1)*heights[i];
			right[i] = (mono_stack.empty() ? n : mono_stack.top());
			mono_stack.push(i);
		}
		int ans = 0;
		for(int i = 0;i<n;i++) {
			ans = max(ans,(right[i]-left[i]-1)*heights[i]);//宽度减1的原因就是左侧哨兵赋值为-1，减去-1，相当于多加了个1要减去
		}
		return ans;
	}
};