class Solution {
public:
vector<int> maximumLengthOfRanges(vector<int>& nums) {
}
};
2832. 每个元素为最大值的最大范围
现给定一个由 不同 整数构成的 0 索引数组 nums 。
我们用以下方式定义与 nums 长度相同的 0 索引数组 ans ：
ans[i] 是子数组 nums[l..r] 的 最大 长度，该子数组中的最大元素等于 nums[i] 。返回数组 ans 。
注意，子数组 是数组的连续部分。
示例 1：
输入：nums = [1,5,4,3,6] 输出：[1,4,2,1,5] 解释：对于 nums[0]，最长的子数组，其中最大值为 1，是 nums[0..0]，所以 ans[0] = 1。 对于 nums[1]，最长的子数组，是 nums[0..3]，其中最大值为 5，所以 ans[1] = 4。 对于 nums[2]，最长的子数组，是 nums[2..3]，其中最大值为 4，所以 ans[2] = 2。 对于 nums[3]，最长的子数组，是 nums[3..3]，其中最大值为 3，所以 ans[3] = 1。 对于 nums[4]，最长的子数组，是 nums[0..4]，其中最大值为 6，所以 ans[4] = 5。
示例 2：
输入：nums = [1,2,3,4,5] 输出：[1,2,3,4,5] 解释：对于 nums[i]，最长的子数组，是 nums[0..i]，其中最大值与 nums[i] 相等，所以 ans[i] = i + 1。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 105nums 中的元素都是不重复的。原站题解
python3 解法, 执行用时: 264 ms, 内存消耗: 41.3 MB, 提交时间: 2023-10-16 22:01:49
class Solution:
def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:
n=len(nums)
left=list(range(n))#左侧起点
right=[n]*n#右侧终点
stack=[]
for i,k in enumerate(nums):
while stack and nums[stack[-1]]<k:
temp=stack.pop()
left[i]=left[temp]
right[temp]=i
stack.append(i)
return [right[i]-left[i] for i in range(n)]
def maximumLengthOfRanges2(self, nums: List[int]) -> List[int]:
has, stark = [[-1, len(nums)] for _ in range(len(nums))], []
for i, v in enumerate(nums):
while stark and nums[stark[-1]] < v: has[stark.pop()][1] = i
if stark: has[i][0] = stark[-1]
stark.append(i)
return [j - i - 1 for i, j in has]
def maximumLengthOfRanges3(self, nums: List[int]) -> List[int]:
nums.append(100001) # 设置哨兵
n = len(nums)
has, stark = [[-1, -1] for _ in range(n)], [-1]
for i in range(n):
v = nums[i]
while nums[stark[-1]] < v: has[stark.pop()][1] = i
has[i][0] = stark[-1]
stark.append(i)
return [j - i - 1 for i, j in has[:-1]]
golang 解法, 执行用时: 172 ms, 内存消耗: 10.2 MB, 提交时间: 2023-10-16 22:01:26
func maximumLengthOfRanges(nums []int) []int {
leftArr, rightArr := make([]int, len(nums)), make([]int, len(nums))
var temp1, temp2 []int
for i := 0; i < len(nums); i++ {
leftIndex, rightIndex := i, len(nums)-i-1
left, right := nums[leftIndex], nums[rightIndex]
for len(temp1) > 0 && nums[temp1[len(temp1)-1]] < left {
leftArr[temp1[len(temp1)-1]] = leftIndex - temp1[len(temp1)-1]
temp1 = temp1[:len(temp1)-1]
}
temp1 = append(temp1, leftIndex)
for len(temp2) > 0 && nums[temp2[len(temp2)-1]] < right {
rightArr[temp2[len(temp2)-1]] = temp2[len(temp2)-1] - rightIndex
temp2 = temp2[:len(temp2)-1]
}
temp2 = append(temp2, rightIndex)
}
res := make([]int, len(nums))
for i := 0; i < len(res); i++ {
if leftArr[i] == 0 {
res[i] += len(nums) - i - 1
} else {
res[i] += leftArr[i] - 1
}
if rightArr[i] == 0 {
res[i] += i
} else {
res[i] += rightArr[i] - 1
}
res[i]++
}
return res
}
java 解法, 执行用时: 21 ms, 内存消耗: 58.5 MB, 提交时间: 2023-10-16 21:59:29
class Solution {
public int[] maximumLengthOfRanges(int[] nums) {
int length = nums.length;
int[] left = new int[length];
int[] right = new int[length];
Arrays.fill(left, -1);
Arrays.fill(right, length);
Deque<Integer> stack = new ArrayDeque<Integer>();
for (int i = 0; i < length; i++) {
int num = nums[i];
while (!stack.isEmpty() && nums[stack.peek()] < num) {
right[stack.pop()] = i;
}
if (!stack.isEmpty()) {
left[i] = stack.peek();
}
stack.push(i);
}
int[] ans = new int[length];
for (int i = 0; i < length; i++) {
ans[i] = right[i] - left[i] - 1;
}
return ans;
}
}
cpp 解法, 执行用时: 220 ms, 内存消耗: 120 MB, 提交时间: 2023-10-16 21:59:13
class Solution {
public:
vector<int> maximumLengthOfRanges(vector<int>& nums) {
int n=nums.size();
stack<int> st;
st.push(-1);//哨兵
vector<int> ans(n);
for(int i=0;i<n;i++){
while(st.size()>1&&nums[st.top()]<nums[i]){
int j=st.top();
st.pop();
ans[j]=i-st.top()-1;
}
st.push(i);
}
while(st.size()>1){
int j=st.top();
st.pop();
ans[j]=n-1-st.top();
}
return ans;
}
};