LeetCode 315 Count of Smaller Numbers After Self

    
        标签：
        
            数组类题目
        
            LeetCode
        
    发布于：2022-03-07 16:55:36
    编辑于：2022-03-07 17:17:58
    浏览量：1085

概述

https://leetcode.com/problems/count-of-smaller-numbers-after-self/

双栈法

芜湖，超时了。

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        stack<int> a, b;
        vector<int> ans(nums.size());
        for (int i = nums.size() - 1; i >= 0; i --) {
            if (!a.empty() && a.top() >= nums[i]) {
                while (!a.empty() && a.top() >= nums[i]) {
                    b.push(a.top());
                    a.pop();
                }
            } else if (!b.empty() && b.top() < nums[i]) {
                while (!b.empty() && b.top() < nums[i]) {
                    a.push(b.top());
                    b.pop();
                }
            }
            b.push(nums[i]);
            ans[i] = a.size();
        }
        return ans;
    }
};

上面的两个 if 可以去掉哦：

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        stack<int> a, b;
        vector<int> ans(nums.size());
        for (int i = nums.size() - 1; i >= 0; i --) {
            while (!a.empty() && a.top() >= nums[i]) {
                b.push(a.top());
                a.pop();
            }
            while (!b.empty() && b.top() < nums[i]) {
                a.push(b.top());
                b.pop();
            }
            b.push(nums[i]);
            ans[i] = a.size();
        }
        return ans;
    }
};

归并排序

TODO

Links: leetcode-315-count-of-smaller-numbers-after-self