index.md

这题的思路比较特殊，这里单独记录一下

暴力法的思路就不再做解释了，应该每个人都可以想到

在学习这个算法之前我们先要明白这里有一个隐含的条件，最大面积时的矩形的上边框一定会和某个矩形的上边框重合

基于这个条件，我们可以通过计算以每一个矩形为基础时的最大面积。 比如 [2,3,1,4],

1. 首先以2为基准高度，因为不能向左延展，所以我们向右做延展，直到找到第一个比2小的元素，此时以2为基准的最大面积是 2 * 2 = 4
2. 再以3为基准高度，向左向右找到第一个比3小的高度，发现2和1，此时已3为基准的最大面积是 3 * 1 = 3，
3. 再以1为基准高度，向左向右找到第一个比1小的高度，发现没有比1小的，此时以1位基准的最大面积是 1 * 4 = 4，
4. 最后以4位基准高度，只能向左找第一个比4小的，发现了1，此时以4为基准高度的最大面积是 4 * 1 = 4，
5. 比较这四种情况的最大面积，得到4

这样算法有一个问题，我需要不断的重复去查找比每一个元素小的数，这就导致了很多重复的执行。 针对这一点，我们可以利用单调栈做优化。

单调栈

之前一直不知道有单调栈这种数据结构，一直没有想出什么比较好的算法解决这题，google 了一下才知道这题需要用到单调栈这种 数据结构才能够较好的解决问题。

首先我们先了解一下什么是单调栈

单调栈是一种单调递增或者单调递减的栈结构 我们可以先自己实现一个简单的单调栈构造函数，

// 这里我们构造一个单调递增的栈,始终保持栈是单调递增的
function create_dull_stack(arr) {
    let stack = [];
    for (let i = 0; i< arr.length; i++) {
        // 如果栈为空或者栈顶的值小于当前值则入栈
        if (stack.length === 0 || stack[stack.length - 1] < arr[i]) {
            stack.push(arr[i]);
        } else {
            // 将比当前元素大的元素出栈
            while (stack.length > 0 && stack[stack.length - 1] > arr[i]) {
                stack.pop();
            }
            // 最后再入栈
            stack.push(arr[i]);
        }
    }
}

然后我们再来看看如何使用单调栈来解决这个问题，首先我们需要单独维护一个单调递增的栈，栈中存放的是 heights 的 index

• 1.首先我们遍历 heights，如果 stack 为空，或者当前height 比 stack 栈顶大，则让height入栈
• 2.如果height 比 stack 栈顶小，则stack 栈顶出栈，并计算以栈顶对应高度为基准的最大面积，根据单调栈的性质，我们可以确定右边第一个比他小的元素就是当前元素，左边第一个比他小的元素就是当前的栈顶，根据两个的差值我们能够计算出以栈顶对应高度为基准的最大面积。
• 3.对比所有情况当中的最大值即为结果

需要注意的地方是，由于可能传进来的heights就是一个单调栈，导致没有执行第二步的出栈，我们再一开始的时候会push一个0到heights末尾

源码