leetcode 84 柱状图中最大的矩阵 思路与C Python实现_最大矩阵和 leetcode

题目地址：84. 柱状图中最大的矩形 - 力扣（LeetCode）
使用哨兵，避免特殊情况的讨论；哨兵技巧的其他应用：
单链表虚拟头结点：避免对真正链表的第一个结点增加或删除作分类讨论；
插入排序：每一次我们都要从后向前进行比较以确定插入元素的位置，同时还要判断是不是比较到头了，
使用哨兵就可以避免每一次都判断，在一定程度上可以加快程序的执行效率；
单调栈：单调栈首先是栈，是栈的应用
栈内元素维持了单调性的应用场景
1、单调递增（不减）栈可以找到左边第一个比当前出栈元素小（包含等于）的元素；
2、单调递减（不增）栈可以找到左边第一个比当前出栈元素大（包含等于）的元素；

注意a[i++] 和a[++i] 的区别：

int a[3] = {0, 1, 2};
int i = 0;
a[i++] = a[2]//数组变成{2, 1, 2}显然在这里是先进行a[i] = a[2]的赋值操作，再对i进行加一操作。
a[++i] = a[2]//数组变成{0, 2, 2}显然在这里是先进行i加一操作，再进行a[i] = a[2]的赋值操作。

常规思路：
1、暴力求解，时间复杂度O(n^3)，因为找最小高度的时间复杂度也是O(n)，这里的n是高度数组的长度；空间复杂度O(1)，使用常数个临时变量。
暴力求解没有保存之前的信息，优化的思路为空间换时间；

for i—>0,n-2{
    for j—i+1，n-1{
        （i，j）—>在i和j中间找最小高度，area
          update max-area
    }
}

2、暴力解法2，枚举棒子；探索棒子左右的边界：向棒子的右边探索新棒子的高度，通过取【新棒子高度和之前minheight】的较小值来维护minheight（初始为一个无穷大的数）；
时间复杂度优化为O(n^2)；

for i—>0,n-1{
    找到left bound，right bound，
    area = hight[i] * (right - left)
    update max-area
}

暴力求解的模板：1、i和j向两边扩散；2、i和j向中间逼近，最后在中间相遇；3、i和j写两个嵌套的循环枚举所有的情况；
3、重新理解栈：栈是辅助的数据结构，保存了遍历过程中的信息；在每一根棒子左右探索新棒子高度的时候存在冗余计算；
时间复杂度O(n)，这里的n是高度数组的长度；空间复杂度O(n)，使用栈的最大保存容量。
本题思路：
维护一个从小到大进行排列的栈（即在入栈时做一些处理使其从栈底到栈顶从小到大排列），因为这样就可以知道他的左边界在什么地方；
入栈的时候把索引也入栈，这样后面方便计算宽度；栈内任何一个元素，他的左边界就是他的下一个元素的索引；
后哨兵的作用：对于一个递增栈来说，可以保证栈内所有元素最后都出栈，避免最后出现栈内元素有剩余的情况；
前哨兵的作用：对于一个递增栈来说，充当一个永不弹出的左起点，保证空栈（前哨兵不算）时可以按照递增的规则进栈；
思路核心：入栈元素小于栈顶元素说明右边界已经确定，需要弹出元素至栈顶元素小于该入栈元素；入栈元素大于栈顶元素，说明右边界尚未确定，可以继续进栈；
配合上前哨兵从而实现递增栈的维护；配合上后哨兵保证最后栈内有效元素全部出栈；哨兵元素一般为-1；

int largestRectangleArea(int* heights, int heightsSize){
    int top = -1;//栈顶指针，top指向的就是此时的栈顶元素，是栈内元素的索引；
    int area, i;//i索引每一根棒子
    int maxarea = 0;
    int *stack = (int *)malloc(sizeof(int) * (heightsSize + 2));//维护的栈，stack[0]始终是前哨兵；
    int *buff = (int *)malloc(sizeof(int) * (heightsSize + 2));//buff就是加完哨兵后的heights
 
    // 在前面加哨兵
    buff[0] = 0;//保证buff[stack[top] = 0，从而保证第一个操作是入栈；
    for (int i = 1; i <= heightsSize; i++) {//heightsSize是数组的长度；
        buff[i] = heights[i - 1];//所有元素进行偏移；
    }
    // 在最后加哨兵；
    buff[heightsSize + 1] = 0;//前后哨兵就是在原heightsSize数组前后各加一个0元素；
 
    stack[++top] = 0;//先进行top+1操作，再进行数组的赋值；先向栈内压入一个前哨兵元素0，他的索引是0；
    for (i = 1; i < heightsSize + 2; i++) {//总共进行了heightsSize+1次循环；buff[i]包含后哨兵，因为要保证所有元素出栈；不包含前哨兵；
        while (top > 0 && buff[i] < buff[stack[top]]) {//出栈条件：1、栈非空（前哨兵不算）；2、入栈元素对应的高小于栈顶元素对应的高；初始值i=1，是因为前哨兵已放入要从buff[1]即第一个有效元素开始放入；这里的"<""保证了前哨兵不出栈，进而避免了下面索引越界；
            area = (i - stack[top - 1] - 1) * buff[stack[top]];//（入栈元素-栈顶元素的前一元素-1）*（栈顶元素对应的高）
            maxarea = maxarea > area ? maxarea : area;//更新最大面积
            top--;//出栈
        }
        stack[++top] = i;//入栈，入栈的元素是heights数组的索引；1——>heightsSize+1；
    }
    return maxarea;
}

测试函数：

void main(){
    int heights[] = {2, 1, 5, 6, 2, 3}, heightsSize = 6, maxarea = 0;
    maxarea = largestRectangleArea(heights, heightsSize);
    printf("maxarea = %d", maxarea);
}

python版本：

class Solution:
    def largestRectangleArea(self, heights):
        maxarea = 0
        buff = [0] + heights + [0]
        stack = [0]
        for i in range(1, len(heights)+2):
            while(len(stack) > 1 and buff[i] < buff[stack[-1]]):
                temp = (i - stack[-2] - 1) * buff[stack[-1]]
                maxarea = max(maxarea, temp)
                stack.pop()
            stack.append(i)
        return maxarea

疑问：1、入栈元素和栈顶元素相等怎么办？