leetcode题解-239-滑动窗口最大值

发表于 2020-01-13 | 更新于 2020-01-14

题目

labuladong way

单调队列

class MonotonicQueue {
private:
    deque<int> data;
public:
    void push(int n) {
        while (!data.empty() && data.back() < n) 
            data.pop_back();
        data.push_back(n);
    }
    
    int max() { return data.front(); }
    
    void pop(int n) {
        if (!data.empty() && data.front() == n)
            data.pop_front();
    }
};

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    MonotonicQueue window;
    vector<int> res;
    for (int i = 0; i < nums.size(); i++) {
        if (i < k - 1) { //先填满窗口的前 k - 1
            window.push(nums[i]);
        } else { // 窗口向前滑动
            window.push(nums[i]);
            res.push_back(window.max());
            window.pop(nums[i - k + 1]);
        }
    }
    return res;
}

不同于一般最大单调栈之处:

只需求滑窗k里面的最大的一个值出来，也就意味着求出最大的max之后，max之前的所有元素可以丢掉了.
仅在滑窗大小 < k时，元素才需push入栈。

References

https://leetcode-cn.com/problems/sliding-window-maximum/solution/dan-diao-dui-lie-by-labuladong/

leetcode题解-901-股票价格跨度

发表于 2020-01-07

题目

单调递增最大栈

class StockSpanner {
private:
    stack<int> prices, cache;

public:
    int next(int price) 
    {
        int w = 1;
        while (!prices.empty() && prices.top() <= price)
        {
            w += cache.top();
            prices.pop();
            cache.pop();
        }
        
        prices.push(price);
        cache.push(w);
        return w;
    }
};

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner* obj = new StockSpanner();
 * int param_1 = obj->next(price);
 */

单调栈模板的伪代码:

Stack stack = new Stack();

for (遍历这个数组)
{
	while (栈不为空 && 栈顶元素小于当前元素)
	{
		栈顶元素出栈;
		对这个出栈值做a操作;
	}
	入栈当前数据;
}

while (栈不为空)
{
	栈顶元素出栈;
	对这个出栈值做b操作;
}

问题在于，因为单调栈是要把元素都丢弃的，状态都被“折叠”了，我们会丢失长度，所以容易想到，我们需要cache一下之前栈内元素被折叠的长度 cache有很多种方式，可以用hash表等数据结构，也可以用动态规划但这题的更优解是，使用另一个同步栈来缓存，读者可以根据下面第一版的代码，动笔推导一下折叠过程，就能体会同步栈工作的原理了。

都说编程旷世难题是取名字，名字取好了，问题也就解决了一半（才怪我们可以将两个栈分别命名为 prices 和 cache

然后就有了下面初版的代码

我们如果发现插入元素满足本身栈的递减需求，则直接返回1，因为该值前一个值是比它大的如果不满足，则开始折叠，并将栈中，值比它小的所有段落都累计起来，再将自己插入栈中即可

总结

单调栈的题目复杂化方法
- 总会在 对出栈值做a操作 和 对出栈值做b操作 这2个地方进行一些复杂化
- 会在 出栈值出栈的存储方式/处理方式 进行一些复杂化的操作

Reference

https://leetcode-cn.com/problems/online-stock-span/solution/gu-piao-jie-ge-kua-du-by-leetcode/

单调栈.md

发表于 2020-01-07 | 分类于总结

单调栈

单调栈模板的伪代码:

Stack stack = new Stack();

for (遍历这个数组)
{
	while (栈不为空 && 栈顶元素小于当前元素)
	{
		栈顶元素出栈;
		对这个出栈值做a操作;
	}
	入栈当前数据;
}

while (栈不为空)
{
	栈顶元素出栈;
	对这个出栈值做b操作;
}

Reference

https://leetcode-cn.com/problems/online-stock-span/solution/dan-diao-zhan-tao-lu-xie-fa-you-hua-wei-guan-fang-/

leetcode题解-739-每日温度

发表于 2020-01-07

题目

My way

最大单调递增栈

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) 
    {
        stack<int> s;
        vector<int> res(T.size());
        unordered_map<int, int> map;

        for (size_t i = 0; i < T.size(); ++i)
        {
            while(!s.empty() && T[s.top()] < T[i])
            {
                map[s.top()] = i - s.top();
                s.pop();
            }

            s.push(i);
        }

        while (!s.empty())
        {
            map[s.top()] = 0;
            s.pop();
        }

        for (size_t i = 0; i < res.size(); ++i)
        {
            res[i] = map[i];
        }

        return res;
    }
};

但是发现时间/空间复杂度都很低，

不应该是所有的元素和右边最大(小)元素都用tuple存放在一个容器内。
而应该遍历的时候就直接将结果存放起来

优化代码结构后：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) 
    {
        stack<int> s;
        vector<int> res(T.size());

        for (size_t i = 0; i < T.size(); ++i)
        {
            while(!s.empty() && T[s.top()] < T[i])
            {
                res[s.top()] = i - s.top();
                s.pop();
            }

            s.push(i);
        }


        return res;
    }
};

Reference

https://leetcode-cn.com/problems/daily-temperatures/solution/mei-ri-wen-du-by-leetcode/

leetcode题解-503-下一个更大元素Ⅱ

发表于 2020-01-07

labuladong way

不严格单调递增栈

vector<int> nextGreaterElements(vector<int>& nums) 
{
    int n = nums.size();
    vector<int> res(n); // 存放结果
    stack<int> s;
    // 假装这个数组长度翻倍了
    for (int i = 2 * n - 1; i >= 0; i--) {
        while (!s.empty() && s.top() <= nums[i % n])
            s.pop();
        res[i % n] = s.empty() ? -1 : s.top();
        s.push(nums[i % n]);
    }
    return res;
}

Why?

为什么这里是用 不严格的单调递增栈 而不是 严格的单调递增栈
为什么通过索引翻倍-1后，是选择方向遍历元素的，而不是正向遍历？

总结

通过索引翻倍-1 和 %运算，来达到模拟数组中元素翻倍的效果。

// 假装这个数组长度翻倍了
for (int i = 2 * n - 1; i >= 0; i--) 
{
	while (!s.empty() && s.top() <= nums[i % n])
		s.pop();
	res[i % n] = s.empty() ? -1 : s.top();
	s.push(nums[i % n]);
}

同时，在元素出栈后，对栈空状态进行判断，
- 若空了则，res对应值为-1
- 若不空则，res对应值为n
- 省去了一个存放tuple的容器的空间大小

Reference

https://leetcode-cn.com/problems/next-greater-element-ii/solution/dan-diao-zhan-jie-jue-next-greater-number-yi-lei-2/

leetcode题解-496-下一个更大元素Ⅰ

发表于 2020-01-06

题目

官方解way

最大单调递增栈

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> map;
        stack<int> s;

        for (int i = 0; i < nums2.size(); ++i)
        {
            while (!s.empty() && s.top() < nums2[i])
            {
                map[s.top()] = nums2[i];
                s.pop();
            }
            s.push(nums2[i]);
        }

        while (!s.empty())
        {
            map[s.top()] = -1;
            s.pop();
        }

        vector<int> vi;
        for (int i = 0; i < nums1.size(); ++i)
        {
            vi.push_back(map[nums1[i]]);
        }

        return vi;
    }
};

最大单调递增栈的流程：

数组中元素依次进栈:

假如栈不为空 且 栈顶元素小于数组当前元素, 则将 栈顶元素出栈 直至 栈不为空 或 栈顶元素大于等于数组当前元素
- 将栈顶元素和第一个大于栈顶(的栈顶右边)元素，形成一个tuple
- 此处是放到unordered_map中来
当前元素进栈
当数组中所有元素遍历完之后，将栈中元素依次弹出
遍历存放tuple的容器

总结

这是一个很经典的单调栈题。

Reference

https://leetcode-cn.com/problems/next-greater-element-i/solution/xia-yi-ge-geng-da-yuan-su-i-by-leetcode/

leetcode题解-42-接雨水

发表于 2020-01-05

题目

官方way

3. (最大)单调递减栈

class Solution {
public:
    int trap(vector<int>& height) 
    {
        stack<int> s;
        int cur = 0;
        int ans = 0;

        while (cur != height.size())
        {
            while (!s.empty() && height[cur] > height[s.top()])
            {
                int top = s.top();
                s.pop();

                if (s.empty())  break;

                int dist = cur - s.top() - 1;
                int bounded_height = min(height[s.top()], height[cur]) - height[top];
                ans += dist * bounded_height;
            }

            s.push(cur++);
        }    

        return ans;
    }
};

维护一个最大单调递减栈的流程如下

让数组中元素依次进栈:

假如栈空，元素直接进栈；
假如栈顶top元素小于数组cur元素，则将数组内元素依次弹出直至：
- 栈顶元素大于数组cur元素
- 栈空
  - 若栈顶元素pop()后且此时栈不为空，
    
    dist = cur - s.top() - 1;,
    
    bounded_height = min(height[s.top()], height[cur]) - height[top];
    
    ans += dist * bounded_height;
    
    由此累加cur元素到top元素的矩形长度进ans;
假如数组中无元素，则对栈中元素依次出栈;

PS：在这里是对数组的索引进行进栈操作，而不是具体到元素。

leetcode题解-199-二叉树的右视图

发表于 2020-01-05

官方解

非递归dfs

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution { 
public:
    vector<int> rightSideView(TreeNode* root) 
    {
        unordered_map<int, int> rightMostValAtDepth;
        stack<TreeNode*> nodeStack;
        stack<int> heightStack;
        int maxDepth = -1;

        nodeStack.push(root);
        heightStack.push(0);

        while(!nodeStack.empty())
        {
            root = nodeStack.top(); nodeStack.pop();
            int depth = heightStack.top(); heightStack.pop();

            if (root)
            {
                maxDepth = max(maxDepth, depth);

                if (!rightMostValAtDepth.count(depth))
                {
                    rightMostValAtDepth[depth] = root->val;
                }

                nodeStack.push(root->left);
                nodeStack.push(root->right);
                heightStack.push(depth+1);
                heightStack.push(depth+1);
            }
        }

        vector<int> vi;
        for (int depth = 0; depth <= maxDepth; ++depth)
        {
            vi.push_back(rightMostValAtDepth[depth]);
        }
        return vi;
    }
};

非递归实现DFS遍历 + 带树高状态

非递归BFS

java实现

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
        int max_depth = -1;

        /* These two Queues are always synchronized, providing an implicit
         * association values with the same offset on each Queue. */
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<Integer> depthQueue = new LinkedList<Integer>();
        nodeQueue.add(root);
        depthQueue.add(0);

        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.remove();
            int depth = depthQueue.remove();

            if (node != null) {
                max_depth = Math.max(max_depth, depth);

                /* The last node that we encounter at a particular depth contains
                * the correct value, so the correct value is never overwritten. */
                rightmostValueAtDepth.put(depth, node.val);

                nodeQueue.add(node.left);
                nodeQueue.add(node.right);
                depthQueue.add(depth+1);
                depthQueue.add(depth+1);
            }
        }

        /* Construct the solution based on the values that we end up with at the
         * end. */
        List<Integer> rightView = new ArrayList<Integer>();
        for (int depth = 0; depth <= max_depth; depth++) {
            rightView.add(rightmostValueAtDepth.get(depth));
        }

        return rightView;
    }
}

C++实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) 
    {
        unordered_map<int, int> rightMostValAtDep;
        queue<TreeNode*> nodeQue;
        queue<int> heightQue;
        int maxDepth = -1;

        nodeQue.push(root);
        heightQue.push(0);

        while(!nodeQue.empty())
        {
            root = nodeQue.front();     nodeQue.pop();
            int height = heightQue.front(); heightQue.pop();

            if (root)
            {
                maxDepth = max(maxDepth, height);

                rightMostValAtDep[height] = root->val;

                nodeQue.push(root->left);
                nodeQue.push(root->right);
                heightQue.push(height+1);
                heightQue.push(height+1);
            }
        }

        vector<int> vi;
        for (int i = 0; i <= maxDepth; ++i)
        {
            vi.push_back(rightMostValAtDep[i]);
        }

        return vi;
    }
};

非递归实现BFS遍历 + 带树高状态

leetcode题解-669-修剪二叉搜索树

发表于 2020-01-02

题目

我的思路是先得到满足要求的节点，再重新构建二叉搜索树，不过显然不是最优解。

官方way

递归 + 状态判断

class Solution {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null) return root;
        if (root.val > R) return trimBST(root.left, L, R);
        if (root.val < L) return trimBST(root.right, L, R);

        root.left = trimBST(root.left, L, R);
        root.right = trimBST(root.right, L, R);
        return root;
    }
}

剪枝思路：

root->val < L,

root及左孩子剪枝，右孩子提升为root
root->val > R

root及右孩子剪枝，左孩子提升为root
L <= root->val && root->val <= R

不需要对root剪枝，递归调用左右孩子

References

https://leetcode-cn.com/problems/trim-a-binary-search-tree/solution/xiu-jian-er-cha-sou-suo-shu-by-leetcode/

leetcode题解-404-左叶子之和

发表于 2020-01-02

Bowen Peng

something about myself and my career development.