1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Given an array of integers nums and an integer limit, return the size of the longest continuous subarray such that the absolute difference between any two elements is less than or equal to limit.
In case there is no subarray satisfying the given condition return 0.
Example 1:
Input: nums = [8,2,4,7], limit = 4 Output: 2 Explanation: All subarrays are: [8] with maximum absolute diff |8-8| = 0 <= 4. [8,2] with maximum absolute diff |8-2| = 6 > 4. [8,2,4] with maximum absolute diff |8-2| = 6 > 4. [8,2,4,7] with maximum absolute diff |8-2| = 6 > 4. [2] with maximum absolute diff |2-2| = 0 <= 4. [2,4] with maximum absolute diff |2-4| = 2 <= 4. [2,4,7] with maximum absolute diff |2-7| = 5 > 4. [4] with maximum absolute diff |4-4| = 0 <= 4. [4,7] with maximum absolute diff |4-7| = 3 <= 4. [7] with maximum absolute diff |7-7| = 0 <= 4. Therefore, the size of the longest subarray is 2.
Example 2:
Input: nums = [10,1,2,4,7,2], limit = 5 Output: 4 Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.
Example 3:
Input: nums = [4,2,2,2,4,4,2,2], limit = 0 Output: 3
Constraints:
1 <= nums.length <= 10^51 <= nums[i] <= 10^90 <= limit <= 10^9
给定一个数组，问数组中一个连续的子数组内的最大值和最小值的差不超过limit的最长连续子数组的长度。
常规解法。使用DP求出任何一个子区间dp[i,j]的最大值和最小值，dp[i,j+1]的最大值和最小值只需要用nums[j]和dp[i,j]的最大值和最小值比较即可。完整代码如下：
class Solution {
public:
int longestSubarray(vector<int>& nums, int limit) {
int n = nums.size();
int ans = 1; // 最小值是1
for (int i = 0; i < n; ++i) {
vector<int> dp_max(n, 0), dp_min(n, INT_MAX);
dp_max[i] = dp_min[i] = nums[i];
for (int len = 2; len <= n; ++len) {
int j = i + len - 1;
if (j >= n)break;
dp_max[j] = max(dp_max[j - 1], nums[j]);
dp_min[j] = min(dp_min[j - 1], nums[j]);
int diff = dp_max[j] - dp_min[j];
if (diff <= limit) {
ans = max(ans, j - i + 1);
}
else {
break;
}
}
}
return ans;
}
};很不幸，该代码的时间复杂度达到了O(n^2)，在最后两个测试样例上TLE了。
比O(n^2)低的复杂度有O(nlgn)和O(n)。O(nlgn)排序好像无法求解，那么只有O(n)的方法了。此题本质上是一个滑动窗口的问题，可以用两个指针i和j，标记区间的起止位置。那么问题的关键就是如何快速求解到区间[i,j]的最大值和最小值。
我之前的方法是用DP提前算出来，但是DP的过程费时。使用优先队列priority_queue（最大堆、最小堆）可以得到当前区域的最大值和最小值，但是一旦差的绝对值超过limit，需要从优先队列中删除i所指元素时，priority_queue没有提供erase或者remove之类的接口，所以使用priority_queue无法达成目标。
提示使用multiset，我之前知道multiset内部使用红黑树结构，内部存储是有序的，而且提供了erase接口以供删除元素。但是我一直不确定如何获得multiset内部的最大值和最小值元素，虽然它内部是有序的，但我不确定程序员能否得到其有序列表。
后来看了multiset的API，里面明确说明了multiset默认是从小到大排序，而且其begin()指向最小值，rbegin()指向最后一个元素，即最大值。所以multiset是一个功能很强大的容器，它不但可以实现堆的功能，还能查找、删除某个元素，比 priority_queue 更强大。
使用multiset的完整代码如下：
class Solution {
public:
int longestSubarray(vector<int>& A, int limit) {
int res = 0, n = A.size(), i = 0, j;
multiset<int> m;
for (j = 0; j < n; ++j) {
m.insert(A[j]);
if (*m.rbegin() - *m.begin() > limit)
m.erase(m.find(A[i++]));
else
res=max(res,j-i+1);
}
return res;
}
};本代码提交AC，用时368MS。