文章目录
- 一，栈
- 1. 用栈操作构建数组
- 2. 逆波兰表达式求值
- 3. 使括号有效的最少添加
- 4. 最小栈
- 5.小行星碰撞
- 6. 验证栈序列
- 7.检查替换后的词是否有效
- 8. 反转每队括号间的子串
- 9.移除无效的括号
- 10. 括号的分数
- 11. 删除字符串后的所有相邻重复项II
- 12. 基本计算器||
- 二，单调栈
- 13.去除重复的字母
- 14.移掉k位数字
- 15.找出具有竞争力的子序列
- 16.132模式
- 17. 每日温度
- 18. 接雨水
- （1）动态规划
- （2）双指针
- （3）单调栈
- 19. 最大宽度坡
- 20.子数组的最小值之和
- 21. 柱状图中最大的矩形
- 22.最大矩形
本文中记录一下在leetcode上中等难度栈和单调栈的一些题解。
一，栈
1. 用栈操作构建数组
题目给你一个n代表往数组中插入从1~n的数据，但是呢它会像栈一样的入栈和出栈。
请你返回合适的操作，因为操作顺序有很多种，所以它答案也是不唯一的。
- 首先呢准备一个num来充当从1~n之间的所有数。
- 然后我们遍历所给的target数组，如果target[i] == num 的话就肯定是push操作。
- 如果先等的话，就将这个元素进行入栈出栈的操作。
char** buildArray(int* target, int targetSize, int n, int* returnSize)
{
char** ans = (char**)malloc(sizeof(char*) * (n * 2));
int size = 0;
int i = 0,num = 1;
for (num = 1; num <= n && i < targetSize; num++)
{
//先入栈
ans[size] = (char*)malloc(sizeof(char) * 5);
strcpy(ans[size++],"Push");
if(target[i] != num)
{
//发现不一致，入栈之后立即出栈，不一致所以 i不动。
ans[size] = (char*)malloc(sizeof(char) * 4);
strcpy(ans[size++],"Pop");
}
else
{
i++;
}
}
*returnSize = size;
return ans;
}
2. 逆波兰表达式求值
这道题要求计算出逆波兰表达式。
- 其思想就是，是数字的话入栈，不是数字的化，将前两个出栈。
- 把前两个值计算出来，再入栈，知道这个数组遍历完成。
- 此时呢栈中会有唯一的元素，这个就是答案。
#define MAX_SIZE 10001
int Helper(int x, int y, char oper)
{
if(oper == '+')
{
return x + y;
}
else if (oper == '-')
{
return x - y;
}
else if (oper == '*')
{
return x * y;
}
else
{
return x / y;
}
}
bool IsDigit(char* s)
{
int i = 0;
while(s[i] != '\0')
{
if(s[i] >= '0' || s[i] <= 9)
{
return true;
}
i++;
}
return false;
}
int evalRPN(char** tokens, int tokensSize)
{
int* stack = (int*)malloc(sizeof(int) * MAX_SIZE);
int top = 0;
int i,ans = 0;
for (i = 0; i < tokensSize; i++)
{
if(IsDigit(tokens[i]))
{
//是数字的话入栈
stack[++top] = atoi(tokens[i]);
}
else
{
//进行操作,取出前两个数
int num2 = stack[top--];
int num1 = stack[top--];
ans = Helper(num1,num2,tokens[i][0]);
//将当前的ans入栈
stack[++top] = ans;
}
}
return stack[top];
}
3. 使括号有效的最少添加
- 思路就是如果栈顶括号可以和外部的括号匹配成（）这个样子，就出栈。
- 否则就入栈。
- 最后栈中有多少括号，就意味着需要补全多少个。
int minAddToMakeValid(char* s)
{
int len = strlen(s);
if(len == 0)
{
return 0;
}
int top = 0;
char* stack = (char*)malloc(sizeof(char) * (len + 1));
stack[++top] = s[0];
for(int i = 1; i < len; i++)
{
if(stack[top] == '(' && s[i] == ')')
{
top--;
}
else
{
stack[++top] = s[i];
}
}
return top;
}
4. 最小栈
这道题要求我们设计一个最小栈出来，就是说每次取其中最小值的时间复杂度是O(1)。
- 我们可以利用两个栈来实现它。
- 一个主栈，存放着所有Push的数据
- 一个副栈，里面存放着最小的数据，栈顶永远是最小的。
- 索引针对于这个副栈来说，当新插入数据的时候于当前栈顶元素去做比较，如果小于等于当前栈顶的元素，那么就将其入栈。
- 而出栈的时候，如果说两边栈的数据一致，那么就同时出栈，否则只出主栈的数据。
#define MAX_SIZE 1000000
typedef struct
{
int* masterStack;
int* minStack;
int masterTop,minTop; //主站和最小栈
} MinStack;
MinStack* minStackCreate()
{
MinStack* obj = (MinStack*)malloc(sizeof(MinStack));
obj -> masterStack = (int*)malloc(sizeof(int) * MAX_SIZE);
obj -> minStack = (int*)malloc(sizeof(int) * MAX_SIZE);
obj -> masterTop = obj -> minTop = 0;
return obj;
}
void minStackPush(MinStack* obj, int val)
{
if(obj -> masterTop + 1 >= MAX_SIZE)
{
printf("空间不足\n");
exit(-1);
}
obj -> masterStack[++(obj -> masterTop)] = val;
if(obj -> minTop == 0 || val <= obj -> minStack[obj -> minTop])
{
//小栈为空或者是新进来的元素比最小栈的元素小。
obj -> minStack[++(obj -> minTop)] = val;
}
}
void minStackPop(MinStack* obj)
{
if(obj -> masterTop == 0) return;
int getTop = obj -> masterStack[(obj -> masterTop)--];
if (getTop == obj -> minStack[(obj -> minTop)])
{
//小栈元素与主栈相同，同时出栈
(obj -> minTop)--;
}
}
int minStackTop(MinStack* obj)
{
if(obj -> masterTop == 0)
{
printf("栈空\n");
exit(-1);
}
return obj -> masterStack[obj -> masterTop];
}
int minStackGetMin(MinStack* obj)
{
if(obj -> masterTop == 0)
{
printf("栈空\n");
exit(-1);
}
return obj -> minStack[obj -> minTop];
}
void minStackFree(MinStack* obj)
{
free(obj -> minStack);
free(obj -> masterStack);
free(obj);
}
/**
* Your MinStack struct will be instantiated and called as such:
* MinStack* obj = minStackCreate();
* minStackPush(obj, val);
* minStackPop(obj);
* int param_3 = minStackTop(obj);
* int param_4 = minStackGetMin(obj);
* minStackFree(obj);
*/
5.小行星碰撞
这道题是给我们一个数组，然后对于数组中有正数和负数，正数朝右移动，负数超左移动，整个数组是同时开始移动的，所以相同方向的两个不会碰撞。
如果两个数体积（绝对值）相同，一起消失。
如果有一个大，那么大的留下来。
- 首先呢拿栈对其进行模拟，如果两个数方向相同呢，入栈。
- 如果不相同则需要判断那一个体积比较大，将大的那个保留下来。
- 还有一种特殊的入栈情况看下图，也就是说，当一个朝左移动，一个朝有移动也是不会碰撞的。
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* asteroidCollision(int* asteroids, int asteroidsSize, int* returnSize)
{
if(asteroidsSize == 1 || asteroidsSize == 0)
{
return asteroids;
}
int* stack = (int*)malloc(sizeof(int) * (asteroidsSize + 1));
int top = 0;
stack[++top] = asteroids[0];
for (int i = 1; i < asteroidsSize; i++)
{
if((stack[top] > 0 && asteroids[i] > 0) || (stack[top] < 0 && asteroids[i] < 0) || (stack[top] < 0 && asteroids[i] > 0))
{
//相同方向，或者是一边朝左边，一边超右边的情况 ···· 入栈
stack[++top] = asteroids[i];
}
else
{
if(abs(stack[top]) < abs(asteroids[i]))
{
//栈顶的体积比它小
i--; //不变，因为循环结束有i++，所以再此i--一下即可实现不变。
top--;
}
else if(abs(stack[top]) == abs(asteroids[i]))
{
//抵消
top--;
}
}
}
*returnSize = top;
return stack + 1;
}
6. 验证栈序列
这道题给了我们两个数组，push数组呢就是必须按照整个顺序进行入栈，但是出栈你随意构造。
然后看看是否能出栈出成pop数组。
- 那么我们首先就创建一个栈，然后进行模拟。
- 对栈进行入栈，入push数组，如果发现栈顶元素和pop栈顶的元素一致，那么我们就行出栈。
- 同时j指向pop中下一个数据。
- 如果最后栈为空，就证明pop这个序列是可行的，否则就不行。
bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize)
{
int* stact = (int*)malloc(sizeof(int) * (pushedSize + 1));
int top = 0;
for (int i = 0, j = 0; i < pushedSize; i++)
{
stact[++top] = pushed[i];
while(top != 0 && stact[top] == popped[j])
{
top--;
j++;
}
}
return top == 0;
}
7.检查替换后的词是否有效
这道题呢就是要求我们将一个空串，通过abc的添加变成串s。
- 同样是构建一个栈出来，去判断栈的前3个是否满足“abc”.
- 如果满足的话就出栈。
bool isValid(char* s)
{
int len = strlen(s);
char* stack = (char*)malloc(sizeof(char) * (len + 1));
int top = 0;
for (int i = 0; i < len; i++)
{
stack[++top] = s[i];
if(top >= 3 && stack[top] == 'c' && stack[top - 1] == 'b' && stack[top - 2] == 'a')
{
top -= 3;
}
}
return top == 0;
}
8. 反转每队括号间的子串
这道题是要求逆序每一层括号内的字符串。
- 我的思路呢就是创建了两个栈，一个存字母，一个存反转的开始位置，也就是左括号。
- 然后如果遇到字母入字母栈.
- 遇到做左括号的话，记录一下需要反转的位置。
- 遇到右括号的话就进行逆序字符串，然后将索引出栈。
void Reverse(char* s,int left, int right)
{
while(left < right)
{
char ch = s[left];
s[left++] = s[right];
s[right--] = ch;
}
}
char* reverseParentheses(char* s)
{
int len = strlen(s);
char* strStcak = (char*)malloc(sizeof(char*) * (len + 1));
int* posStack = (int*)malloc(sizeof(int) * len);
int strTop = 0, posTop = 0;
int i;
for (i = 0; i < len; i++)
{
if(s[i] == '(')
{
posStack[++posTop] = strTop + 1; //记录字符栈中的下标
}
else if(s[i] != ')')
{
//入字符栈
strStcak[++strTop] = s[i];
}
else
{
Reverse(strStcak,posStack[posTop--],strTop);
}
}
strStcak[++strTop] = '\0';
return strStcak + 1;
}
9.移除无效的括号
这道题是给一个字符串，里面包含括号，但是括号包裹的字符串可能不规则，所以需要将括号进行合适的修改，将其去掉一些，从而变成规则的。
- 在之前做过一道匹配括号的题，我们现在同样也是，只针对字符串中的括号进行判断。
- 栈中记录括号的下标，当前字符串遍历完了，会有两种情况。
- 如果栈为空，说明括号全部匹配成功，不需要进行修改。
- 栈不为空，说明栈中有括号未匹配成功，栈中存储的又是下标，直接删除就好了。
char* minRemoveToMakeValid(char* s)
{
int len = strlen(s);
int* stack = (int*)malloc(sizeof(int) * (len + 1));
char* ans = (char*)malloc(sizeof(char) * (len + 1));
int top = 0, pos = 0;
int i;
for (i = 0; i < len; i++)
{
//只针对于括号
if(!isalpha(s[i]))
{
if(top > 0 && s[stack[top]] == '(' && s[i] == ')')
{
top--;
}
else
{
stack[++top] = i; //记录括号下标。
}
}
}
for (int k = 1; k <= top; k++)
{
printf("%d ",stack[k]);
}
//至此呢，栈中会出现没有成功匹配的括号下标
int j = 1;
for (i = 0; i < len && j <= top; i++)
{
if(i != stack[j])
{
ans[pos++] = s[i];
}
else
{
//说明改位置的括未成功匹配，不拷贝
j++;
}
}
//确保源字符串拷贝完成。
while(i < len)
{
ans[pos++] = s[i++];
}
ans[pos] = '\0';
return ans;
}
10. 括号的分数
这道题是要求给定一个字符串，算出字符串的所对应的分数。
题目中AB就是下面这三种情况。
- （） 1分
- （）（） 1 + 1 分
- （（）） 2 * 1 分
我们首先将一个空串s的分数计为0，所以创建好栈好，需要将0入栈。 - 接下来就是对字符串进行遍历，如果遇到（，就将其入栈，入栈的分数是0分。
- 遇到右括号获取栈顶的数据，并对其进行出栈，将下一个栈顶的元素值进行累计相加。
- 注意如果栈顶元素是0，那么就说名此括号配对之后肯定是1 这种情况（）
- 若栈顶元素不是0，就说明里面还有括号，（（））。
int Max(int x, int y)
{
return x > y ? x : y;
}
int scoreOfParentheses(char* s)
{
int len = strlen(s);
int* stack = (int*)malloc(sizeof(int) * (len + 2));
int top = 0;
//栈中第一个元素赋值成0
stack[++top] = 0;
for (int i = 0; i < len; i++)
{
if(s[i] == '(')
{
stack[++top] = 0;
}
else
{
int getTop = stack[top--];
stack[top] += Max(getTop * 2, 1);
}
}
return stack[top];
}
11. 删除字符串后的所有相邻重复项II
这道题呢是要求我们删除所给字符串中，连续出现k次的字符。
- 我们利用两个栈来实现，一个存字符，一个来存记录出现的次数。
- 先将字符入栈，入栈之后判断是否与前一个相等，
- 如果相等，就在前一个出现的次数加1.
- 否则呢，就是刚开始出现，记录次数为1.
- 接着判断是否出现了k次，如果k次了，直接出栈就好了。
char* removeDuplicates(char* s, int k)
{
int len = strlen(s);
char* stackStr = (char*)malloc(sizeof(char) * (len + 2));
int* stackCount = (int*)malloc(sizeof(int) * (len + 2));
int top = 0,i;
for (i = 0; i < len; i++)
{
if(top == 0)
{
stackStr[++top] = s[i];
stackCount[top] = 1;
}
else
{
stackStr[++top] = s[i];
if(stackStr[top] == stackStr[top - 1])
{
stackCount[top] = stackCount[top - 1] + 1;
}
else
{
stackCount[top] = 1;
}
}
//判断是否需要出栈
if(stackCount[top] == k)
{
top -= k;
}
}
stackStr[++top] = '\0';
return stackStr + 1;
}
12. 基本计算器||
实现一个全部由加减乘除而得出的式子，注意其中肯能包含空格
- 首先呢，我们第一边遍历字符串的时候，将数组中的每一个数入栈，如果遇到乘法和除法，先将其结果运算出来再入栈。
- 如果遇到符号是符号的话，将其存储为负数。
- 最后对栈进行就和就好了。
int calculate(char* s)
{
int len = strlen(s);
int* stack = (int*)malloc(sizeof(int) * (len + 1));
int top = 0;
char prevOper = '+'; //前一个操作字符
int i;
long long num = 0;
for (i = 0; i <= len; i++)
{
if(isdigit(s[i]))
{
//是数字
num = num * 10 + s[i] - '0';
}
else if(s[i] != ' ')
{
//操作符
switch(prevOper)
{
case '+':
stack[++top] = num;
break;
case '-':
stack[++top] = -num;
break;
case '*':
stack[top] *= num;
break;
default:
stack[top] /= num;
}
prevOper = s[i];
num = 0;
}
}
int ans = 0;
for (i = 1; i <= top; i++)
{
ans += stack[i];
}
return ans;
}
二，单调栈
13.去除重复的字母
这道题要求将字符串中重复的字符全部消除，使其字典序保证最小，且相对位置不能改变。
- 需要用到哈希表和一个辅助数组visit数组，还有就是栈了
- 哈希表用于记录每个字母所出现的次数。
- visit数组用于标示该字母是否已经入栈。
- 当我们在遍历字符串的时候发现当前字母小于栈顶的元素，并且呢栈顶元素之后还会出现，我们就将其出栈，直到栈为空，或者说是不满足上述两种情况，
- 此时呢，我们再将其入栈，在此过程中维护哈希表和vist数组。
总体的思路就是上面的这些，代码如下:
#define MAX_SIZE 27
char* removeDuplicateLetters(char* s)
{
int* map = (int*)malloc(sizeof(int) * MAX_SIZE); //map 用于记录每个字母所对应的出现次数
int* visit = (int*)malloc(sizeof(int) * MAX_SIZE); //visit 用于标识字母是否已经入栈。
memset(visit,0,sizeof(int) * MAX_SIZE);
memset(map,0,sizeof(int) * MAX_SIZE);
int i, len = strlen(s);
//统计出现的次数,初始化visit数组
for (i = 0; i < len; i++)
{
map[s[i] - 'a']++;
}
//栈。
char* stack = (char*)malloc(sizeof(char) * (len + 2));
int top = 0;
//遍历字符串
for (i = 0; i < len; i++)
{
if(!visit[s[i] - 'a'])
{
//当前数据的字典序小于栈顶的字典序，并且栈数据之后还出现过
while (top != 0 && s[i] < stack[top] && map[stack[top] - 'a'] != 0)
{
//出栈
visit[stack[top] - 'a'] = 0;
top--;
}
//入栈
stack[++top] = s[i];
visit[s[i] - 'a'] = 1;
}
//
map[s[i] - 'a']--;
}
stack[++top] = '\0';
return stack + 1;
}
14.移掉k位数字
这道题和上一道题有点类似，都是使整个字符串序列变得最小。
- 和上题一样需要一个栈来维护。
- 如果当前数据比栈顶小，那么就出栈，
- 反之就进行入栈。
- 但要注意一些边界条件，比如说已经删除了k个字符了，发现小的也没必要出栈了。
- 还有就是如果字符串遍历完了，k还每删除够，说明当前栈中的数据已经是有序的了。直接删除最后k位就好了。
- 最后注意的就是返回时候，记得把前面的0去掉。
char * removeKdigits(char* num, int k)
{
int len = strlen(num);
if(k == len)
{
return "0";
}
char* stack = (char*)malloc(sizeof(char) * (len + 2));
int i, top = 0;
for (i = 0; i < len; i++)
{
while(k != 0 && top != 0 && stack[top] > num[i])
{
//出栈
top--;
k--;
}
//入栈
stack[++top] = num[i];
}
//栈中已经是升序序列，删除末尾即可
while(k != 0)
{
top--;
k--;
}
stack[++top] = '\0';
//去0
i = 1;
while(i < top - 1 && *(stack + i) == '0')
{
i++;
}
return stack + i;
}
15.找出具有竞争力的子序列
这道题和上题一样。。。。。。我是fw，说要留k个，不就是删除numSize - k个嘛？
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* mostCompetitive(int* nums, int numsSize, int k, int* returnSize)
{
if(numsSize == k)
{
*returnSize = numsSize;
return nums;
}
int removeCount = numsSize - k;
int* stack = (int*)malloc(sizeof(int) * (numsSize + 1));
int i, top = 0;
for (i = 0; i < numsSize; i++)
{
while (top != 0 && removeCount != 0 && stack[top] > nums[i])
{
//出栈
top--;
removeCount--;
}
//入栈
stack[++top] = nums[i];
}
while(removeCount != 0)
{
removeCount--;
top--;
}
*returnSize = k;
return stack + 1;
}
16.132模式
这道题是要求我们找出数组中是否满足132这个模式序列，如果满足，那么就返回true
注意i < j < k，所以说不能随便取
- 这道题总的来说就是在遍历的时候进行三次比较嘛。
- 前面的小于中间的(1 < 3)，中间的大于后面的(3>2)，后面的大于前面的(2>1).
- 然后我们可以维护一个prefixMin的一个前缀数组来记录当前位置前面出现的最小值。
- 然后在第二次遍历数组的时候，利用单调栈，就可以选出那个中间的值，和第二个值。
bool find132pattern(int* nums, int numsSize)
{
if(numsSize < 3)
{
return false;
}
int* stack = (int*)malloc(sizeof(int) * (numsSize + 1));
int* prefixMin = (int*)malloc(sizeof(int) * (numsSize + 1));
//构建前缀min
int i, min = INT_MAX, top = 0;
for (i = 0; i < numsSize; i++)
{
if(nums[i] < min)
{
min = nums[i];
}
prefixMin[i] = min;
}
//
for (i = numsSize - 1; i >= 0; i--)
{
int two = INT_MIN; //132 中的2位置.
while(top != 0 && nums[i] > stack[top]) //nums[i] 3 位置，
{
//pop Stcak 3 > 2
two = stack[top--];
}
//is two > prev? 2 > 1 即可 1 3 2
if(two > prefixMin[i])
{
return true;
}
//push stcak
stack[++top] = nums[i];
}
return false;
}
17. 每日温度
这道题和之前做的下一个更大数这类型题是一样的，因为题目中所说的是下一个更大的是第几位，而不是数，所以我们在单调栈中存储其下标即可。
- 如果栈顶数据比当前数组中的数据小，那么就进行出栈，否则就进行入栈的操作。
- 当出栈的时候，同时算出ans.
int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize)
{
int* stack = (int*)malloc(sizeof(int) * (temperaturesSize + 1));
int* ans = (int*)malloc(sizeof(int) * temperaturesSize);
int top = 0,i;
memset(ans,0,sizeof(int) * temperaturesSize);
//
for (i = 0; i < temperaturesSize; i++)
{
while (top != 0 && temperatures[i] > temperatures[stack[top]])
{
int index = stack[top--];
ans[index] = i - index;
}
//push
stack[++top] = i;
}
*returnSize = temperaturesSize;
return ans;
}
18. 接雨水
这道题感觉是要求算出图中蓝色区域的面积，这是一道非常经典的题目,解法也有很多种。
（1）动态规划
最直观的解法就是利用动态规划来做。
- 我们分别求出左边的最大值，和右边的最大值。
- 然后再对数组进行遍历，选出左边和右边最小的值 减去 当前的高度，就是当前积水的面积。ans[i] = Min(leftMax[i] - rightMax[i]) - height[i].
int Max(int x, int y)
{
return x > y ? x : y;
}
int Min(int x, int y)
{
return x < y ? x : y;
}
int trap(int* height, int heightSize)
{
int* leftMax = (int*)malloc(sizeof(int) * heightSize);
int* rightMax = (int*)malloc(sizeof(int) * heightSize);
int i, result = 0;
//left
leftMax[0] = height[0];
for (i = 1; i < heightSize; i++)
{
leftMax[i] = Max(leftMax[i - 1],height[i]);
}
//right
rightMax[heightSize - 1] = height[heightSize - 1];
for (i = heightSize - 2; i >= 0; i--)
{
rightMax[i] = Max(rightMax[i + 1],height[i]);
}
for (i = 0; i < heightSize; i++)
{
result += Min(leftMax[i],rightMax[i]) - height[i];
}
return result;
}
（2）双指针
这个思路其实和上面方法一得思路一致的，只不过是将空间上进行了优化，用2个变量代表了两个数组而已。
- 方法1中是计算出所有得leftMax 和 rightMax，最后再来求解。
- 而双指针是一边算，一边更新最大值。
int Max(int x, int y)
{
return x > y ? x : y;
}
int trap(int* height, int heightSize)
{
int n = heightSize,ans = 0;
int left = 0, right = n - 1;
int leftMax = INT_MIN, rightMax = INT_MIN;
while(left < right)
{
//更新左右最大值
leftMax = Max(leftMax,height[left]);
rightMax = Max(rightMax,height[right]);
if(leftMax < rightMax)
{
ans += leftMax - height[left];
left++;
}
else
{
ans += rightMax - height[right];
right--;
}
}
return ans;
}
（3）单调栈
这道题也可以运用单调栈来解决，可以在遍历一遍的时间上求出答案，不用像方法1种遍历三遍数组。
- 首先维护出一个单调递减的栈出来，当出现的高度比栈顶的高度高的时候，我们就应该计算此凹槽的面积是多少了。
- 而对于此凹槽的面积，的求解，只需要直到它的宽和高即可。
- 那么要计算宽度需要用到下标，高度需要用到每一段对应得值。
- 所以单调栈中应该是存储着数组得下标，这样子可以是求宽度和高度更加方便。
- 我们定义一个left来充当左侧起点，计算出从[left,i]得宽度和高度即可。
int Min(int x, int y)
{
return x < y ? x : y;
}
int trap(int* height, int heightSize)
{
int* stack = (int*)malloc(sizeof(int) * (heightSize + 1));
int top = 0;
int i, result = 0;
for (i = 0; i < heightSize; i++)
{
while(top != 0 && height[i] > height[stack[top]])
{
int getTop = stack[top--];
if(top == 0)
{
//栈中起码得有两个数据才可以进行。
break;
}
int left = stack[top];
int wight = i - left - 1;
int high = Min(height[left],height[i]) - height[getTop];
result += wight * high;
}
stack[++top] = i;
}
return result;
}
19. 最大宽度坡
这道题是求出nums[i] <= nums[j] 的最远距离（i < j）
- 首先创建出一个单调递减的栈。
- 然后从数组的右边也就是末端于栈顶的元素进行比较。
int Max(int x, int y)
{
return x > y ? x : y;
}
int maxWidthRamp(int* nums, int numsSize)
{
int* stack = (int*)malloc(sizeof(int) * (numsSize + 1));
int top = 0, ans = 0, i;
// 创建单单调递减栈
stack[++top] = 0;
for (i = 1; i < numsSize; i++)
{
if(nums[stack[top]] >= nums[i])
{
stack[++top] = i;
}
}
//
for (i = numsSize - 1; i >= 0; i--)
{
while(top != 0 && nums[stack[top]] <= nums[i])
{
ans = Max(ans, i - stack[top]);
top--;
}
if(top == 0)
{
break;
}
}
return ans;
}
20.子数组的最小值之和
这道题使要求出所有子数组中最小值的和。
- 创建一个单调栈（单调递增的栈）和一个dp数组，dp数组用来存放从所对应的下标处子数组的最小值之和。
- 在遍历数组的过程中进行对栈的维护，如果发现栈顶比当前的arr[i]大，说明新加入的数字所新构成的子数组中的最小值将会发生变化，至于发生几组的变化取决于当前的位置 i - 栈中第一个大于arr[i]之间的距离，比如下图：
- 看上图前面几个都是递增的，所以栈不需要进行出栈操作，而当i = 3 时候。
- 43 比 94 81 都小，所以进行出栈操作。
- k * arr[i] + prev prev同样也需要回溯到栈顶的dp去去取值。
- 其中还有一些细节就是对于栈是否为空，如果发现栈为空会有特殊的处理。
- 比如栈都为空了，自然无法取dp数组中的值，所以此时的prev = 0就好了
- 还有就是如果top = 0 k 取成 i + 1，这个条件走画图模拟一下代码就明白了。
#define MAX_SIZE (10001 * 3)
#define MOD 1000000007
int sumSubarrayMins(int* arr, int arrSize)
{
int* stack = (int*)malloc(sizeof(int) * MAX_SIZE);
int* dp = (int*)malloc(sizeof(int) * MAX_SIZE);
int top = 0;
long long result = 0, tmp = 0;
for (int i = 0; i < arrSize; i++)
{
while(top != 0 && arr[i] < arr[stack[top]])
{
//出栈
top--;
}
int k = (top == 0 ? i + 1 : i - stack[top]);
dp[i] = arr[i] * k + (top == 0 ? 0 : dp[stack[top]]);
result = (result + dp[i]) % MOD;
stack[++top] = i;
}
return result % MOD;
}
21. 柱状图中最大的矩形
这道题要求我们求出所给柱子可以构成的最大面接，这道题和接雨水很相似，但是感觉这个比接雨水要难。
自己本来也不是很会，很清楚，感觉代码随想录的思路很好，讲的以恶可以学习。
- 就上面这4副图呢，我们可以发现，只要求出对应的长度和高度就好了。
- 长度就是left + right - 1, 高度就是它自身mid的值。
- 同样也可以发现，左右都是对于mid的第一个最小元素。
- 至于为什么前面后面需要加 0看下图。
- 对于一下两幅图，图一会发现遍历到第一个数据时候找到了right和mid却找不到left
- 而对与右边的图片来说，会发现遍历完数组，都不会找到right。
- 所以需要两边加上0来计算
int Max(int x, int y)
{
return x > y ? x : y;
}
int largestRectangleArea(int* heights, int heightsSize)
{
int n = heightsSize;
int i = 0, result = 0;
//首位添加0
int* changeArr = (int*)malloc(sizeof(int) * (n + 2));
changeArr[0] = 0;
changeArr[n + 1] = 0;
for (i = 0; i < n; i++)
{
changeArr[i + 1] = heights[i];
}
//
int* stack = (int*)malloc(sizeof(int) * (n + 3));
int top = 0;
for (i = 0; i < n + 2; i++)
{
while(top != 0 && changeArr[i] < changeArr[stack[top]])
{
//出栈
int left = stack[top - 1],mid = stack[top--]; //left mid right = i;
result = Max(result, (i - left - 1) * changeArr[mid]);
}
stack[++top] = i;
}
return result;
}
22.最大矩形
这道题是要求我们算所给矩阵中包含1的最大矩形面积。
这道题和上面的那道柱状图中最大的矩形面积是很类似的，上一图中是一个数组，而这道题中是一堆数组，我们可以将二维数组简单的拆分一下,如下图：
可以发现，求出每一层的柱状图最大的面积，然后对其再选出最大的即可。
这样就将一个二维数组，转化成求解一维矩阵的问题。
那如何获取修改后的二维数组，我们可以用一个二维的dp数组来解决
- 从上图就可以发现，dp数组初始化第一层，就是原来数组的第一层。
- 而状态转移方程则取决于当前是否是0 .
- dp[i][j] = (matrix[i][j] == ‘0’ ? 0 : dp[i - 1][j] + 1)
看下面的代码中的largestRectangleArea函数就是上一题中。
int maximalRectangle(char** matrix, int matrixSize, int* matrixColSize)
{
int i,j, row = matrixSize, col = matrixColSize[0];
int** dp = (int**)malloc(sizeof(int * ) * row);
for (i = 0; i < row; i++)
{
dp[i] = (int*)malloc(sizeof(int) * col);
}
//初始化第一行
for (i = 0; i < col; i++)
{
dp[0][i] = matrix[0][i] - '0';
}
int result = largestRectangleArea(dp[0],col);
//创建dp数组
for (i = 1; i < row; i++)
{
for (j = 0; j < col; j++)
{
dp[i][j] = (matrix[i][j] == '0' ? 0 : dp[i - 1][j] + 1);
}
//并且算出每一行的最大矩形面积
result = Max(result,largestRectangleArea(dp[i],col));
}
return result;
}
