刷题日常 | LeetCode面试经典150题

---

这一篇博客主要记录一下在刷LeetCode面试经典150题中遇到的一些有趣的题目。

所有题解或笔者自编或来源于LeetCode官方。

数组/字符串

55.跳跃游戏

题目

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例

示例 1

输入：nums = [2,3,1,1,4]

输出：true

解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2

输入：nums = [3,2,1,0,4]

输出：false

解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

题解

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int i = 0 , steps= nums[0] , n = nums.size();
        for(i = 1;i<n && steps>0;++i)
        {
            steps = max(steps-1,nums[i]);
            if(steps>= n - 1 - i)
            {
                return true;
            }
        }
        return i == n;
    }
};

第一次做直接贪心算法写递归函数，然后时间超限了（意料之内）。不要被题目的“跳跃”给误导了，如果从还可以走多少步的角度思考问题就迎刃而解了。

时间复杂度$O(n)$，空间复杂度$O(1)$.

42.接雨水

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例

示例一

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]

输出：6

解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例二

输入：height = [4,2,0,3,2,5]

输出：9

题解

题解一：动态规划

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0) {
            return 0;
        }
        vector<int> leftMax(n);
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = max(leftMax[i - 1], height[i]);
        }

        vector<int> rightMax(n);
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
};

从左往右看和从右往左看，记录每个位置前面的最高挡板分别是多高。然后每个位置能接到的实际水量就是min(leftMax[i], rightMax[i]) - height[i]。

比较简单易懂，也很好写。

时间复杂度$O(n)$，空间复杂度$O(n)$.

题解二：双指针

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        int left = 0, right = height.size() - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
};

由题解一可以引出题解二的思路，每个盛水的地块能盛水数实际是由两侧较矮的挡板决定，因此可以记录左右两侧的最高者lefMax和rightMax，在遍历数组同时不断尝试更新较矮者的值。

感觉非常巧妙，if(height[left] < height[right])这个判断条件有点难想到。

时间复杂度$O(n)$，空间复杂度$O(1)$.

题解三：单调栈

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        stack<int> stk;
        int n = height.size();
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && height[i] > height[stk.top()]) {
                int top = stk.top();
                stk.pop();
                if (stk.empty()) {
                    break;
                }
                int left = stk.top();
                int currWidth = i - left - 1;
                int currHeight = min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stk.push(i);
        }
        return ans;
    }
};

不断将数组下标放入栈中，当有元素值大于栈最顶上的下标对应的值时，说明这一层可以盛水，取出最顶上的元素，计算长宽后加入结果，再重复判断该元素值还是否大于栈最顶上的下标对应的值。实际上就是，对于每一个能装水的区域，逐层计算能装的水体积。

对栈的理解运用非常厉害！挖掘题目本质，值得学习。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$.

这道题也是在没接触算法之前就久闻大名了，没想到有这么多思路，自己尝试也是磨了很久才搞定，运行时间还被薄纱了。