算法总结*单调栈

单调栈

  • 单调栈包括单调递增栈和单调递减栈
  • 单调递增栈:单调递增栈就是从栈底到栈顶数据是从小到大
  • 单调递减栈:单调递减栈就是从栈底到栈顶数据是从大到小

算法实现

void largestRectangleArea(int* heights, int heightsSize){
    int orderStack[LARGEST_AREA_STACK_SIZE] = {0};
    int top = -1;
    for (int i = 0; i < heightsSize; i++) {
        if (top == -1 || heights[i] >= heights[orderStack[top]]) {
            orderStack[++top] = i;
            continue;
        }
        while (top >= 0 && heights[orderStack[top]] > heights[i]) {
            top--;
        }
        orderStack[++top] = i;
    }
    while (top >= 0) {
        top--;
    }
    return;
}

算法描述

参考例题

剑指 Offer
原文地址:https://www.cnblogs.com/kunlingou/p/14588847.html