| comments | difficulty | edit_url | tags | |||
|---|---|---|---|---|---|---|
true |
中等 |
|
给你一个长度为 n 的整数数组 nums ，你需要处理 n 个查询。
对于第 i （0 <= i < n）个查询：
- 你需要先找出
nums的所有长度为i + 1的子数组中的 最小值 。 - 在这些最小值中找出 最大值 作为答案。
返回一个 下标从 0 开始 的长度为 n 的整数数组 ans ，ans[i] 代表第 i 个查询的答案。
示例 1：
输入: nums = [0,1,2,4] 输出: [4,2,1,0] 解释: i = 0: - 大小为 1 的子数组为 [0], [1], [2], [4] - 有最大的最小值的子数组是 [4], 它的最小值是 4 i = 1: - 大小为 2 的子数组为 [0,1], [1,2], [2,4] - 有最大的最小值的子数组是 [2,4], 它的最小值是 2 i = 2: - 大小为 3 的子数组为 [0,1,2], [1,2,4] - 有最大的最小值的子数组是 [1,2,4], 它的最小值是 1 i = 3: - 大小为 4 的子数组为 [0,1,2,4] - 有最大的最小值的子数组是 [0,1,2,4], 它的最小值是 0
示例 2：
输入: nums = [10,20,50,10] 输出: [50,20,10,10] 解释: i = 0: - 大小为 1 的子数组为 [10], [20], [50], [10] - 有最大的最小值的子数组是 [50], 它的最小值是 50 i = 1: - 大小为 2 的子数组为 [10,20], [20,50], [50,10] - 有最大的最小值的子数组是 [20,50], 它的最小值是 20 i = 2: - 大小为 3 的子数组为 [10,20,50], [20,50,10] - 有最大的最小值的子数组是 [10,20,50], 它的最小值是 10 i = 3: - 大小为 4 的子数组为 [10,20,50,10] - 有最大的最小值的子数组是 [10,20,50,10], 它的最小值是 10
提示：
n == nums.length1 <= n <= 1050 <= nums[i] <= 109
我们可以先利用单调栈，求出每个位置的左边第一个比它小的位置
然后我们遍历数组，对于每个位置
接着我们倒序遍历数组，更新
最后返回
时间复杂度
class Solution:
def findMaximums(self, nums: List[int]) -> List[int]:
n = len(nums)
left = [-1] * n
right = [n] * n
stk = []
for i, x in enumerate(nums):
while stk and nums[stk[-1]] >= x:
stk.pop()
if stk:
left[i] = stk[-1]
stk.append(i)
stk = []
for i in range(n - 1, -1, -1):
while stk and nums[stk[-1]] >= nums[i]:
stk.pop()
if stk:
right[i] = stk[-1]
stk.append(i)
ans = [0] * n
for i in range(n):
m = right[i] - left[i] - 1
ans[m - 1] = max(ans[m - 1], nums[i])
for i in range(n - 2, -1, -1):
ans[i] = max(ans[i], ans[i + 1])
return ansclass Solution {
public int[] findMaximums(int[] nums) {
int n = nums.length;
int[] left = new int[n];
int[] right = new int[n];
Arrays.fill(left, -1);
Arrays.fill(right, n);
Deque<Integer> stk = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
while (!stk.isEmpty() && nums[stk.peek()] >= nums[i]) {
stk.pop();
}
if (!stk.isEmpty()) {
left[i] = stk.peek();
}
stk.push(i);
}
stk.clear();
for (int i = n - 1; i >= 0; --i) {
while (!stk.isEmpty() && nums[stk.peek()] >= nums[i]) {
stk.pop();
}
if (!stk.isEmpty()) {
right[i] = stk.peek();
}
stk.push(i);
}
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
int m = right[i] - left[i] - 1;
ans[m - 1] = Math.max(ans[m - 1], nums[i]);
}
for (int i = n - 2; i >= 0; --i) {
ans[i] = Math.max(ans[i], ans[i + 1]);
}
return ans;
}
}class Solution {
public:
vector<int> findMaximums(vector<int>& nums) {
int n = nums.size();
vector<int> left(n, -1);
vector<int> right(n, n);
stack<int> stk;
for (int i = 0; i < n; ++i) {
while (!stk.empty() && nums[stk.top()] >= nums[i]) {
stk.pop();
}
if (!stk.empty()) {
left[i] = stk.top();
}
stk.push(i);
}
stk = stack<int>();
for (int i = n - 1; i >= 0; --i) {
while (!stk.empty() && nums[stk.top()] >= nums[i]) {
stk.pop();
}
if (!stk.empty()) {
right[i] = stk.top();
}
stk.push(i);
}
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
int m = right[i] - left[i] - 1;
ans[m - 1] = max(ans[m - 1], nums[i]);
}
for (int i = n - 2; i >= 0; --i) {
ans[i] = max(ans[i], ans[i + 1]);
}
return ans;
}
};func findMaximums(nums []int) []int {
n := len(nums)
left := make([]int, n)
right := make([]int, n)
for i := range left {
left[i], right[i] = -1, n
}
stk := []int{}
for i, x := range nums {
for len(stk) > 0 && nums[stk[len(stk)-1]] >= x {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
left[i] = stk[len(stk)-1]
}
stk = append(stk, i)
}
stk = []int{}
for i := n - 1; i >= 0; i-- {
x := nums[i]
for len(stk) > 0 && nums[stk[len(stk)-1]] >= x {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
right[i] = stk[len(stk)-1]
}
stk = append(stk, i)
}
ans := make([]int, n)
for i := range ans {
m := right[i] - left[i] - 1
ans[m-1] = max(ans[m-1], nums[i])
}
for i := n - 2; i >= 0; i-- {
ans[i] = max(ans[i], ans[i+1])
}
return ans
}