907 Sum of Subarray Minimums

For each A[I], find the first number on the left that is less than it, and the first number on the right that is less than or equal to it, using monotone stack. Note that the processing of equal numbers must be less than and equal to

class Solution {
public:
    int modn = 1e9 + 7;
    long long ml[30005], mr[30005];
    int sumSubarrayMins(vector<int>& A) {
        int n = A.size();
        stack<pair<int, int>> stl, str;
        stl.push(make_pair(-1e9, -1));
        for(int i = 0; i < n; i++)
        {
            while(A[i] < stl.top().first)
                stl.pop();
            ml[i] = i - stl.top().second;
            stl.push(make_pair(A[i], i));
        }
        str.push(make_pair(-1e9, n));
        for(int i = n - 1; i >= 0; i--)
        {
            while(A[i] <= str.top().first)
                str.pop();
            mr[i] = str.top().second - i;
            str.push(make_pair(A[i], i));
        }
        long long ans = 0;
        for(int i = 0; i < n; i++)
        { cout << ml[i] <<' '<< mr[i]<<endl;
            ans = (ans + A[i] * ml[i] % modn * mr[i] % modn) % modn;
        }
        returnans; }};Copy the code

915 Partition Array into Disjoint Intervals

Let’s not talk about water

918 Maximum Sum Circular Subarray

Calculate the maximum subsegment sum and the smallest subsegment sum, compare the sum of the largest subsegment and the sum of the smallest subsegment, and take the larger value among them; There is a special case where all negative numbers require special treatment

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        int n = A.size();
        long long sum = 0;
        for(int i = 0; i < n; i++)
            sum += A[i];
        long long maxs = -1e9, mins = 1e9, s = 0;
        for(int i = 0; i < n; i++)
        {
            s += A[i];
            maxs = max(maxs, s);
            if(s <= 0)
                s = 0;
        }
        s = 0;
        for(int i = 0; i < n; i++)
        {
            s += A[i];
            mins = min(mins, s);
            if(s >= 0)
                s = 0;
        } //cout<< sum << ' ' << mins <<' '<< maxs<<endl;
        if(mins == sum)
            return maxs;
        returnmax(maxs, sum - mins); }};Copy the code

926 Flip String to Monotone Increasing

Is the water problem

945 Minimum Increment to Make Array Unique

Sort first, then make sure A[I] >= A[i-1] + 1

class Solution {
public:
    int minIncrementForUnique(vector<int>& A) {
        sort(A.begin(), A.end());
        int n = A.size();
        int ans = 0;
        for(int i = 1; i < n; i++)
        {
            if(A[i] <= A[i - 1]) { ans += A[i - 1] - A[i] + 1; A[i] = A[i - 1] + 1; }}returnans; }};Copy the code

950 Reveal Cards In Increasing Order

Linked list simulation

class Solution { public: struct Link { int id; struct Link* next; Link(int x) { id = x; next = nullptr; }}; vector<int> deckRevealedIncreasing(vector<int>& deck) { sort(deck.begin(), deck.end()); int n = deck.size(); Link* head, *tail;for(int i = 0; i < n; i++)
        {
            Link *node = new Link(i);
            if(i == 0)
                head = tail = node;
            else
            {
                tail -> next = node;
                tail = node;
            } 
        }
        vector<int> ans(n);
        int i = 0;
        while(true)
        {
            ans[head -> id] = deck[i++]; 
            if(head -> next ! = nullptr) { head = head -> next; tail -> next = head; tail = head; head = head -> next; tail -> next = nullptr; }else
                break;
        }
        returnans; }};Copy the code