-
Notifications
You must be signed in to change notification settings - Fork 639
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
给你一个数组[2,1,2,4,3],你返回数组 [4,2,4,−1,−1] #142
Labels
Comments
|
function arrFormat(arr){
let _arr = []
for (let index = 0; index < arr.length; index++) {
const val = arr[index];
//找出这个值之后的数组
const afterArr = arr.slice(index,arr.length)
//找出第一个最大值的index
const firstBiggerIndex = afterArr.findIndex(afterVal=>{
return afterVal > val
})
if(firstBiggerIndex > -1){
_arr.push(afterArr[firstBiggerIndex])
}else{
_arr.push(-1)
}
}
console.log('_arr',_arr)
return _arr
}
arrFormat([2,1,2,4,3]) |
时间复杂度O(n) function arrFormat(arr: number[]): number[]{
const len: number = arr.length;
const stack: number[] = [arr[0]];
const ret: number[] = new Array(len).fill(-1);
const map: Record<number, number[]> = arr.reduce((acc: Record<number, number[]>, key: number, index: number) => {
if (acc[key]) {
acc[key].push(index);
} else {
acc[key] = [index];
}
return acc;
}, Object.create(null));
for (let i: number = 1; i < len; i++) {
const cur = arr[i];
while (cur > stack[stack.length - 1]) {
const key: number = stack.pop() as number;
const index: number = map[key].pop() as number;
ret[index] = cur;
}
stack.push(cur);
}
return ret;
} |
const arr = [2,1,2,4,3]
const f = arr => {
if(!arr.length) return []
const len = arr.length
let l = 0,
r = l + 1,
res = []
while(res.length < len) {
let cur = arr[l],
next = arr[r]
if(next > cur) {
res.push(next)
l += 1
r = l + 1
}else if(r >= len - 1){
res.push(-1)
l += 1
r = l + 1
}else {
r += 1
}
}
return res
}
const result = f(arr)
console.log(result) |
|
|
const arr = [2, 1, 2, 4, 3];
const result = arr.map((m, index) => {
const t = arr.slice(index).find(n => n > m);
return t === undefined ? -1 : t;
});
console.log(result); |
这个应该放在数据结构「栈」里,这道题其实考察的是单调栈,原题其实是 LeetCode 503: 下一个更大元素 II |
function nextGreaterElements(nums: number[]): number[] {
let stack: number[] = [];
let res: number[] = new Array(nums.length).fill(-1);
let len = nums.length;
for(let i = 2 * len - 1; i >= 0; i--) {
while(stack.length !== 0 && stack[stack.length - 1] <= nums[i % len]) {
stack.pop();
}
res[i % len] = stack.length === 0 ? -1 : stack[stack.length - 1];
stack.push(nums[i % len]);
}
return res;
}; |
var nextGreaterElements = function (nums) {
let res = new Array(nums.length).fill(-1)
let stack = []
stack.push(0)
let numsLen = nums.length
for (let i = 1, len = nums.length; i < len; i++) {
while (stack.length && nums[i ] > nums[stack[stack.length - 1]]) {
res[stack[stack.length - 1]] = nums[i]
stack.pop()
}
stack.push(i)
}
return res
}; |
function getFistMax(nums){
let res = new Array(nums.length).fill(-1)
let stack = []
for(let i=0;i<nums.length;i++){
while(stack.length&&nums[i]>nums[stack[stack.length-1]]){
let top = stack.pop()
res[top] = nums[i]
}
stack.push(i)
}
return res
}
console.log(getFistMax([2,1,2,4,3])) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
给你一个数组
[2,1,2,4,3]
,你返回数组[4,2,4,−1,−1]
解释:
第一个
2
后面比2
大的数是4
;1
后面比1
大的数是2
;第二个2
后面比2
大的数是4
;4
后面没有比4
大的数,填-1
;3
后面没有比3
大的数,填-1
。The text was updated successfully, but these errors were encountered: