Leetcode game 295

summary

The conclusion is that you are too good , The monotonous stack needs more practice , Most of the time, monotone stack may not be the best value for simple maintenance . The second question focuses on library functions , The third question is the simple use of monotone stack , It was really not difficult after the game , But I don't know why I was crying when I was playing ~ Purring

6079. Price reduction

Not familiar with library functions hh, But I just learned . Because there was no special judgment, I sent another one

class Solution {
    
public:
    long long check(string s) {
    
        if (s.empty()) return false;
        for (auto & c : s)
            if (!isdigit(c))
                return false;
        return stoll(s);
    }
    string discountPrices(string s, int d) {
    
        stringstream ss(s);
        string str;
        string ans;
        while (ss >> str) {
    
            ans += " ";
            if (str[0] != '$') {
    
                ans += str;
                continue;
            } else {
    
                long long t = check(str.substr(1));
                if (t) {
    
                    char c[20] = {
    };
                    cout << t << endl;
                    sprintf(c, "$%.2lf", (double)t * 1.0 * (100 - d) / 100);
                    ans += c;
                }
                else ans += str;
            }
        }
    return ans.substr(1);
    }
};

6080. Make the array in non decreasing order

class Solution {
    
public:
    int totalSteps(vector<int> &nums) {
    
        int ans = 0;
        stack<pair<int, int>> st;
        for (int num : nums) {
    
            int maxT = 0;
            while (!st.empty() && st.top().first <= num) {
    
                maxT = max(maxT, st.top().second);
                st.pop();
            }
            if (!st.empty()) ++maxT;
            ans = max(ans, maxT);
            st.emplace(num, maxT);
        }
        return ans;
    }
};

6081. The minimum number of obstacles that need to be removed to reach the corner

// shiran
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define sz(x) (int)size(x)
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
#define mk make_mair
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 1e9+7;
const int N = 200010, M = 300010;
int dx[4] = {
    -1, 0, 1, 0}, dy[4] = {
    0, 1, 0, -1};

struct Node
{
    
    int x, y, d;
    bool operator< (const Node &t) const
    {
    
        return d > t.d;
    }
};

class Solution {
    
public:
    int minimumObstacles(vector<vector<int>>& grid) {
    
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> f(n, vector<int>(m, INF));
        priority_queue<Node> q;
        q.push({
    0, 0, 0});
        f[0][0] = 0;
        
        while (q.size())
        {
    
            auto t = q.top(); q.pop();
            
            if (t.x == n - 1 && t.y == m - 1) break;
            
            rep(i, 0, 4)
            {
    
                int x = t.x + dx[i], y = t.y + dy[i];
                if (x < 0 || x >= n || y < 0 || y >= m) continue;
                if (f[x][y] > f[t.x][t.y] + grid[x][y])
                {
    
                    f[x][y] = f[t.x][t.y] + grid[x][y];
                    q.push({
    x, y, f[x][y]});
                }
            }
        }
        return f[n - 1][m - 1];
    }
};