单调栈

单调栈

单调栈简单来说是在栈的先进后出基础之上额外添加一个特性：从栈顶到栈底的元素是严格递增（or递减）
具体进栈过程如下：
对于单调递增栈，若当前进栈元素为 e，从栈顶开始遍历元素，把小于 e 或者等于 e 的元素弹出栈，直接遇到一个大于 e 的元素或者栈为空为止，然后再把 e 压入栈中。
对于单调递减栈，则每次弹出的是大于 e 或者等于 e 的元素。

举个例子，将[3，4，2，6，4，5，2，3] 从左至右入栈，按单调递增栈形式进行入栈，即要插入栈顶的元素e入栈前必须比之前栈顶的元素小或相等(这样才符合从栈顶到栈底的元素时严格递增的)，否则就不停地弹出栈顶元素，直到满足条件为止。换句话说，也就是必须要遇到大于插入栈顶元素e的元素或者栈为空时，e才入栈。

可以对于单调递增栈而言，发现每次进栈操作后，栈顶元素e左边元素都是原数组中该元素e左边第一个大于它的数。

单调栈例题：

问题描述：

在横轴上放了n个相邻的矩形，每个矩形的宽度是1，而第i（1 ≤ i ≤ n）个矩形的高度是hi。这n个矩形构成了一个直方图。例如，下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。

请找出能放在给定直方图里面积最大的矩形，它的边要与坐标轴平行。对于上面给出的例子，最大矩形如下图所示的阴影部分，面积是10。

输入格式

第一行包含一个整数n，即矩形的数量(1 ≤ n ≤ 1000)。
第二行包含n 个整数h1, h2, … , hn，相邻的数之间由空格分隔。(1 ≤ hi ≤ 10000)。hi是第i个矩形的高度。

输出格式

输出一行，包含一个整数，即给定直方图内的最大矩形的面积。

样例输入

6
3 1 6 5 2 3

样例输出

10

import java.util.LinkedList;
import java.util.Scanner;

public class Main3 extends Thread {

	public static void main(String[] args) {
		new Main3().run();
	}

	@Override
	public void run() {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] h = new int[n + 1];
		for (int i = 0; i < n; i++) {
			h[i] = scanner.nextInt();
		}
		h[n] = -1;
		scanner.close();

		int maxArea = 0;
		LinkedList<Integer> stack = new LinkedList<>();
		for (int i = 0; i < n + 1; i++) {
			while (!stack.isEmpty() && h[i] < h[stack.peek()]) {
				int maxH = h[stack.peek()];
				stack.pop();
				int left = stack.isEmpty() ? -1 : stack.peek();
				int maxW = i - (left + 1);
				maxArea = Math.max(maxArea, maxW * maxH);
			}
			stack.push(i);
			System.out.println(stack);
		}
		System.out.println(maxArea);
	}
}