【2023】字节跳动 10 日心动计划——第三关

1. 最长有效括号

🔗 原题链接：32. 最长有效括号

类似于有效的括号，考虑用栈来解决。

具体来讲，我们始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标。

从左往右遍历整个字符串，如果遇到 (，则将其下标压入栈中；如果遇到 )，则先弹出栈顶元素，然后再判断栈是否为空，如果栈为空，说明当前的右括号为没有被匹配的右括号，将其压入栈中，否则，更新答案。

注意，任何时刻，只有栈底元素是右括号的下标，其他元素都是左括号的下标！

class Solution {
public:int longestValidParentheses(string s) {stack<int> stk;int ans = 0;stk.push(-1);for (int i = 0; i < s.size(); i++) {if (s[i] == '(') stk.push(i);else {stk.pop();if (stk.empty()) stk.push(i);else ans = max(ans, i - stk.top());}}return ans;}
};

2. 有序数组的平方

🔗 原题链接：977. 有序数组的平方

这里介绍两种做法。

方法一：找到正负元素的分界线，然后对正、负数组进行二路归并。

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int p = lower_bound(nums.begin(), nums.end(), 0) - nums.begin();int i = p, j = p - 1;vector<int> res;while (i < nums.size() && j >= 0) {int a = pow(nums[i], 2), b = pow(nums[j], 2);if (a <= b) res.push_back(a), i++;else res.push_back(b), j--;}while (i < nums.size()) {int a = pow(nums[i], 2);res.push_back(a);i++;}while (j >= 0) {int b = pow(nums[j], 2);res.push_back(b);j--;}return res;}
};

方法二：同样使用双指针。之前我们是让两个指针从中间往两边移动，这次我们让两个指针从两边往中间移动，所以填答案的时候需要倒着填。

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int n = nums.size();vector<int> res(n);int i = 0, j = n - 1, k = n - 1;while (i <= j) {int a = nums[i] * nums[i];int b = nums[j] * nums[j];if (a >= b) res[k] = a, i++;else res[k] = b, j--;k--;}return res;}
};