中等题 ----- 栈和单调栈

文章目录

  • 一,栈
    • 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;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/389344.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

opencv鼠标响应与操作

这节讲得好,建议仔细揣摩 Point sp(-1, -1);//初始位置 Point ep(-1, -1);//结束位置 Mat temp; static void on_draw(int event, int x, int y, int flags, void * userdata) {Mat image *((Mat*)userdata);//先将void类型转为Mat类型//((Mat*)userdata)是Mat类型指针 前面加…

vue3 中使用pinia 数据状态管理(在Taro 京东移动端框架中的使用)

1.pinia 介绍 pinia 是 Vue 的存储库&#xff0c;它允许您跨组件/页面共享状态。就是和vuex一样的实现数据共享。 依据Pinia官方文档&#xff0c;Pinia是2019年由vue.js官方成员重新设计的新一代状态管理器&#xff0c;更替Vuex4成为Vuex5。 Pinia 目前也已经是 vue 官方正式的…

论文阅读 - Non-Local Spatial Propagation Network for Depth Completion

文章目录 1 概述2 模型说明2.1 局部SPN2.2 非局部SPN2.3 结合置信度的亲和力学习2.3.1 传统正则化2.3.2 置信度引导的affinity正则化 3 效果3.1 NYU Depth V23.2 KITTI Depth Completion 参考资料 1 概述 本文提出了一种非局部的空间传播网络用于深度图补全&#xff0c;简称为…

手把手教你免费搭建自己的红包封面商城​

您好&#xff0c;我是码农飞哥&#xff08;wei158556&#xff09;&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。&#x1f4aa;&#x1f3fb; 1. Python基础专栏&#xff0c;基础知识一网打尽&#xff0c;9.9元买不了吃亏&#xff0c;买不了上当。 Python从入门到精通…

【Linux】调试工具gdb:初识

前言 今天来记录并学习一下gdb的使用 背景 程序的发布方式有两种&#xff0c;debug模式和release模式Linux gcc/g出来的二进制程序&#xff0c;默认是release模式要使用gdb调试&#xff0c;必须在源代码生成二进制程序的时候, 加上 -g 选项 使用 gdb FileName 退出&#x…

爱上JVM——常见问题:JVM组成(一)

1 JVM组成 1.1 JVM由那些部分组成&#xff0c;运行流程是什么&#xff1f; 难易程度&#xff1a;☆☆☆ 出现频率&#xff1a;☆☆☆☆ JVM是什么 Java Virtual Machine Java程序的运行环境&#xff08;java二进制字节码的运行环境&#xff09; 好处&#xff1a; 一次编写&…

qt-C++笔记之打印所有发生的事件

qt-C笔记之打印所有发生的事件 code review! 文章目录 qt-C笔记之打印所有发生的事件1.ChatGPT问答使用 QApplication 的 notify 方法使用 QObject 的 event 方法 2.使用 QObject 的 event 方法3.使用 QApplication 的 notify 方法 1.ChatGPT问答 在Qt C中&#xff0c;若要打…

相机图像质量研究(22)常见问题总结:CMOS期间对成像的影响--光学串扰

系列文章目录 相机图像质量研究(1)Camera成像流程介绍 相机图像质量研究(2)ISP专用平台调优介绍 相机图像质量研究(3)图像质量测试介绍 相机图像质量研究(4)常见问题总结&#xff1a;光学结构对成像的影响--焦距 相机图像质量研究(5)常见问题总结&#xff1a;光学结构对成…

C# VS2022+WinForm+Oracle19.3+Excel,根据数据库表定义书生成SQL

目标&#xff1a; 用Excel写数据库的表的定义书&#xff0c;用该工具生成SQL&#xff0c;在客户端执行&#xff0c;把表结构导入数据库&#xff0c;生成真正的表 Github代码下载 目录 0.完成下面开发环境的准备1 操作系统Win11 专业版 21H22 oracle 19.33 Visual Studio Commun…

C语言第二十五弹---字符函数和字符串函数(上)

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】 目录 1、字符分类函数 2、字符转换函数 3、strlen的使用和模拟实现 4、strcpy 的模拟实现 5、strcat 的模拟实现 6、strcmp 的模拟实现 7、strncpy 函数的使用 总结…

高效货运 - 华为OD统一考试(C卷)

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 200分 题解&#xff1a; Java / Python / C 题目描述 老李是货运公司承运人&#xff0c;老李的货车额定载货重量为wt&#xff1b;现有两种货物&#xff0c;货物A单件重量为wa&#xff0c;单件运费利润为pa&#xff0c…

Fluke ADPT 连接器新增对福禄克万用 Fluke 15B Max 的支持

所需设备&#xff1a; 1、Fluke ADPT连接器&#xff1b; 2、Fluke 15B Max&#xff1b; Fluke 15B Max拆机图&#xff1a; 显示界面如下图&#xff1a; 并且可以将波形导出到EXCEL: 福禄克万用表需要自己动手改造&#xff01;&#xff01;&#xff01;

【C++第二阶段-重载-关系运算符函数调用】

你好你好&#xff01; 以下内容仅为当前认识&#xff0c;可能有不足之处&#xff0c;欢迎讨论&#xff01; 文章目录 关系运算符-重载-判断相等函数调用运算符重载 关系运算符-重载-判断相等 场景&#xff1a;两个对象&#xff0c;若有年龄和性别的不同&#xff0c;是否可以直…

AI数据中心网络架构需求:400/800G光模块

随着AI技术和相关应用的不断发展&#xff0c;大模型、大数据和AI计算能力在AI发展中的重要性日益凸显。大模型和数据集构成AI研究的软件基础&#xff0c;而AI算力是关键的基础设施。在本文中&#xff0c;我们将探讨AI发展对数据中心网络架构的影响。 Fat-Tree数据中心网络架构…

Spring Boot结合MinIO 实现文件切片极速上传!

本文将介绍如何使用Spring Boot和MinIO实现文件切片极速上传技术&#xff0c;通过将大文件分割成小片段并并行上传&#xff0c;显著提高文件上传速度。 2 文件切片上传简介 文件切片上传是指将大文件分割成小的片段&#xff0c;然后通过多个请求并行上传这些片段&#xff0c;最…

【C++】实现Date类的各种运算符重载

上一篇文章只实现了operator操作符重载&#xff0c;由于运算符较多&#xff0c;该篇文章单独实现剩余所有的运算符重载。继续以Date类为例&#xff0c;实现运算符重载&#xff1a; 1.Date.h #pragma once#include <iostream> #include <assert.h>using namespace …

相机图像质量研究(24)常见问题总结:CMOS期间对成像的影响--摩尔纹

系列文章目录 相机图像质量研究(1)Camera成像流程介绍 相机图像质量研究(2)ISP专用平台调优介绍 相机图像质量研究(3)图像质量测试介绍 相机图像质量研究(4)常见问题总结&#xff1a;光学结构对成像的影响--焦距 相机图像质量研究(5)常见问题总结&#xff1a;光学结构对成…

【面试】盘点10个高频的前端算法题,你全都会了吗?

前言 &#x1f4eb; 大家好&#xff0c;我是南木元元&#xff0c;热爱技术和分享&#xff0c;欢迎大家交流&#xff0c;一起学习进步&#xff01; &#x1f345; 个人主页&#xff1a;南木元元 现在前端的面试中&#xff0c;算法出现的频率越来越高了&#xff0c;大厂更是必考算…

GPIO八种工作模式

目录 一、推挽输出 二、开漏输出 三、复用推挽输出 四、复用开漏输出 五、浮空输入 六、上拉输入 七、下拉输入 八、模拟输入 GPIO八种配置模式&#xff0c;原理和使用场景&#xff0c;硬件原理如下图&#xff1a; 一、推挽输出 1、 原理 当控制栅极为低电平时&#x…

【Visual Studio】使用空格替换制表符

环境 VS版本&#xff1a;VS2013 问题 如何生成空格替换制表符&#xff1f; 步骤 1、菜单 工具->选项&#xff0c;文本编辑器->C/C->制表符&#xff0c;选择【插入空格】。