当前位置： 首页 > news >正文

LeetCode每日一题JAVA、JavaSrcipt题解——2022.08.11-08.20

news 来源：原创 2024/4/29 7:44:27

title: 2022-08-11-1417-重新格式化字符串
date: 2022-08-11 9:51:12
tags: [Daily Practice, 字符串, 简单题]
categories: 算法题

1417. 重新格式化字符串

JAVA

class Solution {
    public String reformat(String s) {
        // 如果数字和字母数量相差大于2，肯定无法格式化
        int digitCount = 0;
        int alphaCount = 0;
        char[] arr = s.toCharArray();
        for (char c : arr) {
            if (Character.isDigit(c)) {
                digitCount++;
            } else {
                alphaCount++;
            }
        }

        if (Math.abs(digitCount - alphaCount) > 1) {
            return "";
        }

        if (digitCount >= alphaCount) {
            helper(arr, true);
        } else {
            helper(arr, false);
        }

        return new String(arr);
    }

    private void helper(char[] arr, boolean digitFirst) {
        int p1 = 0; // 偶数下标
        int p2 = 1; // 奇数下标

        while (p1 < arr.length) {
            if (digitFirst) {
                // 优先使用数字
                // 那么，偶数下标存储数字，奇数下标存储字母
                if (!Character.isDigit(arr[p1])) {
                    // 如果p1的位置不是数字，就从p2的位置找一个数字换过来
                    // 如果p2位置不是数字，就往后找，直到找到一个数字为止
                    while (!Character.isDigit(arr[p2])) {
                        p2 += 2;
                    }
                    swap(arr, p1, p2);
                }
                p1 += 2;
            } else {
                // 优先使用字母
                // 那么，偶数下标存储字母，奇数下标存储数字
                if (Character.isDigit(arr[p1])) {
                    while (Character.isDigit(arr[p2])) {
                        p2 += 2;
                    }
                    swap(arr, p1, p2);
                }
                p1 += 2;
            }
        }
    }

    private void swap(char[] arr, int i, int j) {
        char tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

JS

var reformat = function(s) {
    let sumDigit = 0;
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (isDigit(c)) {
            sumDigit++;
        }
    }
    let sumAlpha = s.length - sumDigit;
    if (Math.abs(sumDigit - sumAlpha) > 1) {
        return "";
    }
    let flag = sumDigit > sumAlpha;
    const arr = [...s];
    for (let i = 0, j = 1; i < s.length; i += 2) {
        if (isDigit(arr[i]) !== flag) {
            while (isDigit(arr[j]) !== flag) {
                j += 2;
            }
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    return arr.join('');
}

const isDigit = (ch) => {
    return parseFloat(ch).toString() === "NaN" ? false : true;
}

title: 2022-08-12-1282-用户分组
date: 2022-08-12 18:51:12
tags: [Daily Practice, 哈希, 中等题]
categories: 算法题

1282. 用户分组

在这里插入图片描述
在这里插入图片描述

JS

/**
 * @param {number[]} groupSizes
 * @return {number[][]}
 */
var groupThePeople = function(groupSizes) {
    const groups = new Map();
    const n = groupSizes.length;
    for (let i = 0; i < n; i++) {
        const size = groupSizes[i];
        if (!groups.has(size)) {
            groups.set(size, []);
        }
        groups.get(size).push(i);
    }
    const groupList = [];
    for (const [size, people] of groups.entries()) {
        const groupCount = Math.floor(people.length / size);
        for (let i = 0; i < groupCount; i++) {
            const group = [];
            const start = i * size;
            for (let j = 0; j < size; j++) {
                group.push(people[start + j]);
            }
            groupList.push(group);
        }
    }
    return groupList;
};

JAVA

//我们维护一张哈希表，key为人所在的组的大小，value为第i个人，当size等于key时，划分为1个组。    
public List<List<Integer>> groupThePeople(int[] groupSizes) {
        int n = groupSizes.length;
        List<List<Integer>> ans = new ArrayList<>();
        //n+1的哈希表
        ArrayList[] hash = new ArrayList[n + 1];
        for (int i = 0; i < groupSizes.length; i++) {
            //哈希表的key
            int key = groupSizes[i];
            if (hash[key] == null) {
                hash[key] = new ArrayList();
            }
            //添加人
            hash[key].add(i);
            //组内人数和key相同 划分为一个组
            if (hash[key].size() == key) {
                ans.add(new ArrayList<>(hash[key]));
                hash[key].clear();
            }
        }
        return ans;
    }

title: 2022-08-13-768-最多能完成排序的块 II
date: 2022-08-13 18:51:12
tags: [Daily Practice, 排序, 困难题]
categories: 算法题

768. 最多能完成排序的块 II

JAVA

// class Solution {
//     public int maxChunksToSorted(int[] arr) {
//         int[] cln = arr.clone();
//         Arrays.sort(cln);
//         // pref = sum(arr[0] to arr[i]) - sum(cln[0] to cln[i])
//         int pref = 0, chunks = 0;
//         for (int i = 0; i < arr.length; ++i)
//             if ((pref += arr[i] - cln[i]) == 0)
//                 ++chunks;
//         return chunks;
//     }
// }

//贪心加构造  哈希
class Solution {
    public int maxChunksToSorted(int[] arr) {
        int[] clone = arr.clone();
        Arrays.sort(clone);
        int n = arr.length, ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0, tot = 0; i < n; i++) {
            int a = arr[i], b = clone[i];
            if (map.getOrDefault(a, 0) == -1) tot--;
            else if (map.getOrDefault(a, 0) == 0) tot++;
            map.put(a, map.getOrDefault(a, 0) + 1);
            if (map.getOrDefault(b, 0) == 1) tot--;
            else if (map.getOrDefault(b, 0) == 0) tot++;
            map.put(b, map.getOrDefault(b, 0) - 1);
            if (tot == 0) ans++;
        }
        return ans;
    }
}

JS

var maxChunksToSorted = function(arr) {
    const cnt = new Map();
    let res = 0;
    const sortedArr = new Array(arr.length).fill(0);
    sortedArr.splice(0, arr.length, ...arr);
    sortedArr.sort((a, b) => a - b);
    for (let i = 0; i < sortedArr.length; i++) {
        const x = arr[i], y = sortedArr[i];
        cnt.set(x, (cnt.get(x) || 0) + 1);
        if (cnt.get(x) === 0) {
            cnt.delete(x);
        }
        cnt.set(y, (cnt.get(y) || 0) - 1);
        if (cnt.get(y) === 0) {
            cnt.delete(y);
        }
        if (cnt.size === 0) {
            res++;
        }
    }
    return res;
};


var maxChunksToSorted = function(arr) {
    const stack = [];
    for (const num of arr) {
        if (stack.length === 0 || num >= stack[stack.length - 1]) {
            stack.push(num);
        } else {
            const mx = stack.pop();
            while (stack.length && stack[stack.length - 1] > num) {
                stack.pop();
            }
            stack.push(mx);
        }
    }
    return stack.length;
};

title: 2022-08-14-1422-分割字符串的最大得分
date: 2022-08-14 20:51:12
tags: [Daily Practice, 字符串, 前缀和, 模拟, 简单题]
categories: 算法题

1422. 分割字符串的最大得分

在这里插入图片描述

前缀和
构建前缀和数组来记录每个前缀中 11 个个数，复杂度为 O(n) O(n)，枚举每个分割点，搭配前缀和数组计算左串中 00 的数量和右串中 11 的数量，取所有得分的最大值即是答案。

JAVA

class Solution {
    public int maxScore(String s) {
        int l = s.length(), ans = 0;
        int [] sum = new int[l + 1];
        for (int i = 1; i <= l; i++) {
            sum[i] = sum[i - 1] + (s.charAt(i - 1) - '0'); 
        }
        for (int i = 1; i <= l - 1; i++) {
            int a = i - sum[i], b = sum[l] - sum[i];
            ans = Math.max(ans, a + b);
        }
        return ans;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var maxScore = function(s) {
    let l = s.length, ans = 0;
    let sum = new Array(l + 1);
    sum[0] = 0;
    for (let i = 1; i <= l; i++) {
        sum[i] = sum[i - 1] + parseInt(s.charAt(i - 1) - '0'); 
    }
    for (let i = 1; i <= l - 1; i++) {
        let a = i - sum[i], b = sum[l] - sum[i];
        ans = Math.max(ans, a + b);
    }
    return ans;
};

在这里插入图片描述

class Solution {
    public int maxScore(String s) {
        int n = s.length(), cur = s.charAt(0) == '0' ? 1 : 0;
        for (int i = 1; i < n; i++) {
            cur += s.charAt(i) - '0';
        }
        int ans = cur;
        for (int i = 1; i < n - 1; i++) {
            cur += s.charAt(i) == '0' ? 1 : -1;
            ans = Math.max(ans, cur);
        }
        return ans;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var maxScore = function(s) {
    let l = s.length, cur = s.charAt(0) == '0' ? 1 : 0;
    for (let i = 1; i < l; i++) {
        cur += s.charAt(i) - '0';
    }
    let ans = cur;
    for (let i = 1; i < l - 1; i++) {
        cur += s.charAt(i) == '0' ? 1 : -1;
        ans = Math.max(ans, cur);
    }
    return ans;
};

title: 2022-08-15-641-设计循环双端队列
date: 2022-08-15 20:51:12
tags: [Daily Practice, 队列, 数据结构, 中等题]
categories: 算法题

641. 设计循环双端队列

JAVA

class MyCircularDeque {
    private int[] elements;
    private int rear, front;
    private int capacity;

    public MyCircularDeque(int k) {
        capacity = k + 1;
        rear = front = 0;
        elements = new int[k + 1];
    }

    public boolean insertFront(int value) {
        if (isFull()) {
            return false;
        }
        front = (front - 1 + capacity) % capacity;
        elements[front] = value;
        return true;
    }

    public boolean insertLast(int value) {
        if (isFull()) {
            return false;
        }
        elements[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }

    public boolean deleteFront() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        return true;
    }

    public boolean deleteLast() {
        if (isEmpty()) {
            return false;
        }
        rear = (rear - 1 + capacity) % capacity;
        return true;
    }

    public int getFront() {
        if (isEmpty()) {
            return -1;
        }
        return elements[front];
    }

    public int getRear() {
        if (isEmpty()) {
            return -1;
        }
        return elements[(rear - 1 + capacity) % capacity];
    }

    public boolean isEmpty() {
        return rear == front;
    }

    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }
}

JS

/**
 * @param {number} k
 */
var MyCircularDeque = function(k) {
    this.ary = new Array()
    this.length = k
};

/** 
 * @param {number} value
 * @return {boolean}
 */
MyCircularDeque.prototype.insertFront = function(value) {
    if(this.ary.length < this.length) {
        this.ary.unshift(value)
        return true
    } else {
        return false
    }
};

/** 
 * @param {number} value
 * @return {boolean}
 */
MyCircularDeque.prototype.insertLast = function(value) {
    if(this.ary.length < this.length) {
        this.ary.push(value)
        return true
    } else {
        return false
    }
};

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.deleteFront = function() {
    if(this.ary.length > 0) {
        this.ary.shift()
        return true
    }else {
        return false
    }
};

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.deleteLast = function() {
    if(this.ary.length > 0) {
        this.ary.pop()
        return true
    } else {
        return false
    }
};

/**
 * @return {number}
 */
MyCircularDeque.prototype.getFront = function() {
    if(this.ary.length > 0) {
        return this.ary[0]
    } else {
        return -1
    }
};

/**
 * @return {number}
 */
MyCircularDeque.prototype.getRear = function() {
    if(this.ary.length > 0) {
        return this.ary[this.ary.length-1]
    } else {
        return -1
    }
};

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.isEmpty = function() {
    return this.ary.length == 0
};

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.isFull = function() {
    return this.ary.length == this.length
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * var obj = new MyCircularDeque(k)
 * var param_1 = obj.insertFront(value)
 * var param_2 = obj.insertLast(value)
 * var param_3 = obj.deleteFront()
 * var param_4 = obj.deleteLast()
 * var param_5 = obj.getFront()
 * var param_6 = obj.getRear()
 * var param_7 = obj.isEmpty()
 * var param_8 = obj.isFull()
 */

title: 2022-08-16-1656-设计有序流
date: 2022-08-16 14:51:12
tags: [Daily Practice, 模拟, 数据结构, 简单题]
categories: 算法题

1656. 设计有序流

JAVA

class OrderedStream {
    //感觉类似哈希存字符串
    String[] ss = new String[1010];
    int idx, n;
    public OrderedStream(int _n) {
        Arrays.fill(ss, "");//初始化
        idx = 1; //当前指针
        n = _n;
    }
    public List<String> insert(int key, String value) {
        ss[key] = value;
        List<String> ans = new ArrayList<>();
        while (ss[idx].length() == 5) {
            ans.add(ss[idx++]);
        }
        return ans;
    }
}


/**
 * Your OrderedStream object will be instantiated and called as such:
 * OrderedStream obj = new OrderedStream(n);
 * List<String> param_1 = obj.insert(idKey,value);
 */

/**
 * @param {number} n
 */
var OrderedStream = function(n) {
    this.ptr = 1;
    this.mStream = [];
};

/** 
 * @param {number} id 
 * @param {string} value
 * @return {string[]}
 */
OrderedStream.prototype.insert = function(id, value) {
    this.mStream[id] = value;
    var res = [];
    //只有当前插入得id等于ptr才可能返回有序流，否则不会返回
    if(id === this.ptr){
        //ptr依次往后走，直到在数组中找不到这个key为止
        while(this.ptr in this.mStream){
            res.push(this.mStream[this.ptr++]);
        }
    }
    return res;
};

/**
 * Your OrderedStream object will be instantiated and called as such:
 * var obj = new OrderedStream(n)
 * var param_1 = obj.insert(id,value)
 */

title: 2022-08-17-1302-层数最深叶子节点的和
date: 2022-08-17 14:51:12
tags: [Daily Practice, 二叉树, dfs, bfs, 中等题]
categories: 算法题

1302. 层数最深叶子节点的和

dfs

JAVA

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxLevel = -1;
    int sum = 0;

    public int deepestLeavesSum(TreeNode root) {
        dfs(root, 0);
        return sum;
    }

    public void dfs(TreeNode node, int level) {
        if (node == null) {
            return;
        }
        if (level > maxLevel) {
            maxLevel = level;
            sum = node.val;
        } else if (level == maxLevel) {
            sum += node.val;
        }
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
}

JS

var deepestLeavesSum = function(root) {
    let maxLevel = -1;
    let sum = 0;
    const dfs = (node, level) => {
        if (!node) {
            return;
        }
        if (level > maxLevel) {
            maxLevel = level;
            sum = node.val;
        } else if (level === maxLevel) {
            sum += node.val;
        }
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    dfs(root, 0);
    return sum;
};

bfs

JAVA

class Solution {
    public int deepestLeavesSum(TreeNode root) {
        int sum = 0;
        Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            sum = 0;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                sum += node.val;
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return sum;
    }
}

JS

var deepestLeavesSum = function(root) {
    let sum = 0;
    const queue = [];
    queue.push(root);
    while (queue.length) {
        sum = 0;
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            sum += node.val;
            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
        }
    }
    return sum;
};

title: 2022-08-18-1224
date: 2022-08-18 20:51:12
tags: [Daily Practice, 哈希, 模拟, 困难题]
categories: 算法题

1224. 最大相等频率

在这里插入图片描述

JAVA

class Solution {
    public int maxEqualFreq(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
        Map<Integer, Integer> count = new HashMap<Integer, Integer>();
        int res = 0, maxFreq = 0;
        for (int i = 0; i < nums.length; i++) {
            if (count.getOrDefault(nums[i], 0) > 0) {
                freq.put(count.get(nums[i]), freq.get(count.get(nums[i])) - 1);
            }
            count.put(nums[i], count.getOrDefault(nums[i], 0) + 1);
            maxFreq = Math.max(maxFreq, count.get(nums[i]));
            freq.put(count.get(nums[i]), freq.getOrDefault(count.get(nums[i]), 0) + 1);
            boolean ok = maxFreq == 1 ||
                    freq.get(maxFreq) * maxFreq + freq.get(maxFreq - 1) * (maxFreq - 1) == i + 1 && freq.get(maxFreq) == 1 ||
                    freq.get(maxFreq) * maxFreq + 1 == i + 1 && freq.get(1) == 1;
            if (ok) {
                res = Math.max(res, i + 1);
            }
        }
        return res;
    }
}

JS

var maxEqualFreq = function(nums) {
    const freq = new Map();
    const count = new Map();
    let res = 0, maxFreq = 0;
    for (let i = 0; i < nums.length; i++) {
        if (!count.has(nums[i])) {
            count.set(nums[i], 0);
        }
        if (count.get(nums[i]) > 0) {
            freq.set(count.get(nums[i]), freq.get(count.get(nums[i])) - 1);
        }
        count.set(nums[i], count.get(nums[i]) + 1);
        maxFreq = Math.max(maxFreq, count.get(nums[i]));
        if (!freq.has(count.get(nums[i]))) {
            freq.set(count.get(nums[i]), 0);
        }
        freq.set(count.get(nums[i]), freq.get(count.get(nums[i])) + 1);
        const ok = maxFreq === 1 ||
                freq.get(maxFreq) * maxFreq + freq.get(maxFreq - 1) * (maxFreq - 1) === i + 1 && freq.get(maxFreq) === 1 ||
                freq.get(maxFreq) * maxFreq + 1 === i + 1 && freq.get(1) === 1;
        if (ok) {
            res = Math.max(res, i + 1);
        }
    }
    return res;
};

计数模拟——三叶姐

class Solution {
    static int[] cnt = new int[100010], sum = new int[100010];
    public int maxEqualFreq(int[] nums) {
        Arrays.fill(cnt, 0); Arrays.fill(sum, 0);
        int n = nums.length, max = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            int t = nums[i], cur = ++cnt[t], len = i + 1;
            sum[cur]++; sum[cur - 1]--;
            max = Math.max(max, cur);
            if (max == 1) ans = len;
            if (max * sum[max] + 1 == len) ans = len;
            if ((max - 1) * (sum[max - 1] + 1) + 1 == len) ans = len;
        }
        return ans;
    }
}

title: 2022-08-19-1450-在既定时间做作业的学生人数
date: 2022-08-19 10:51:12
tags: [Daily Practice, 模拟, 简单题]
categories: 算法题

1450. 在既定时间做作业的学生人数

在这里插入图片描述

模拟

JAVA

class Solution {
    public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
        int cnt = 0;
        for (int i = 0; i < startTime.length; i++) {
            if (startTime[i] <= queryTime && endTime[i] >= queryTime) {
                cnt++;
            }
        }
        return cnt;
    }
}

JS

/**
 * @param {number[]} startTime
 * @param {number[]} endTime
 * @param {number} queryTime
 * @return {number}
 */
var busyStudent = function(startTime, endTime, queryTime) {
    let cnt = 0;
    for (let i = 0; i < startTime.length; i++) {
        cnt += (startTime[i] <= queryTime && endTime[i] >= queryTime) ? 1 : 0;
    }
    return cnt;
};

差分

在这里插入图片描述

class Solution {
    public int busyStudent(int[] st, int[] et, int t) {
        int[] c = new int[1010];
        for (int i = 0; i < st.length; i++) {
            c[st[i]]++; 
            c[et[i] + 1]--;
        }
        for (int i = 1; i <= t; i++) c[i] += c[i - 1];
        return c[t];
    }
}

JS

/**
 * @param {number[]} startTime
 * @param {number[]} endTime
 * @param {number} queryTime
 * @return {number}
 */
var busyStudent = function(startTime, endTime, queryTime) {
    var c = new Array(1010).fill(0);
    var l = startTime.length;
    for (let i = 0; i < l; i++) {
        c[startTime[i]]++;
        c[endTime[i] + 1]--;
    }

    for (let i = 1; i <= queryTime; i++) {
        c[i] += c[i - 1];
    }
    return c[queryTime];
};

title: 2022-08-20-654-最大二叉树
date: 2022-08-20 22:01:12
tags: [Daily Practice, 二叉树, 中等题, 栈]
categories: 算法题

654. 最大二叉树

递归模拟

在这里插入图片描述

JAVA

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return construct(nums, 0, nums.length - 1);
    }

    public TreeNode construct(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        int best = left;
        for (int i = left + 1; i <= right; ++i) {
            if (nums[i] > nums[best]) {
                best = i;
            }
        }
        TreeNode node = new TreeNode(nums[best]);
        node.left = construct(nums, left, best - 1);
        node.right = construct(nums, best + 1, right);
        return node;
    }
}

JS

var constructMaximumBinaryTree = function(nums) {
    const construct = (nums, left, right) => {
        if (left > right) {
            return null;
        }
        let best = left;
        for (let i = left + 1; i <= right; ++i) {
            if (nums[i] > nums[best]) {
                best = i;
            }
        }
        const node = new TreeNode(nums[best]);
        node.left = construct(nums, left, best - 1);
        node.right = construct(nums, best + 1, right);
        return node;
    }
    return construct(nums, 0, nums.length - 1);
};

单调栈

在这里插入图片描述

三叶的

class Solution {
    static TreeNode[] stk = new TreeNode[1010];
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        int he = 0, ta = 0;
        for (int x : nums) {
            TreeNode node = new TreeNode(x);
            while (he < ta && stk[ta - 1].val < x) node.left = stk[--ta];
            if (he < ta) stk[ta - 1].right = node;
            stk[ta++] = node;
        }
        return stk[0];
    }
}

JAVA

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        int n = nums.length;
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(left, -1);
        Arrays.fill(right, -1);
        TreeNode[] tree = new TreeNode[n];
        for (int i = 0; i < n; ++i) {
            tree[i] = new TreeNode(nums[i]);
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                right[stack.pop()] = i;
            }
            if (!stack.isEmpty()) {
                left[i] = stack.peek();
            }
            stack.push(i);
        }

        TreeNode root = null;
        for (int i = 0; i < n; ++i) {
            if (left[i] == -1 && right[i] == -1) {
                root = tree[i];
            } else if (right[i] == -1 || (left[i] != -1 && nums[left[i]] < nums[right[i]])) {
                tree[left[i]].right = tree[i];
            } else {
                tree[right[i]].left = tree[i];
            }
        }
        return root;
    }
}

JS

var constructMaximumBinaryTree = function(nums) {
    const n = nums.length;
    const stack = [];
    const left = new Array(n).fill(-1);
    const right = new Array(n).fill(-1);
    const tree = new Array(n).fill(-1);
    for (let i = 0; i < n; ++i) {
        tree[i] = new TreeNode(nums[i]);
        while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
            right[stack.pop()] = i;
        }
        if (stack.length) {
            left[i] = stack[stack.length - 1];
        }
        stack.push(i);
    }

    let root = null;
    for (let i = 0; i < n; ++i) {
        if (left[i] === -1 && right[i] === -1) {
            root = tree[i];
        } else if (right[i] === -1 || (left[i] !== -1 && nums[left[i]] < nums[right[i]])) {
            tree[left[i]].right = tree[i];
        } else {
            tree[right[i]].left = tree[i];
        }
    }
    return root;
};

相关文章：

  • java面向对象思维程序设计开发以及案例 -电梯运行问题对象分析与程序设计(2)
  • 有限元和神经网络结合,人脑神经网络和宇宙
  • 手写一个二叉搜索树（BST）
  • 高通WLAN框架学习（36）-- ACS（Auto Channel Selection）自动信道选择
  • 程序流程控制（Java）
  • 分布式事务seata入门
  • 深度神经网络训练
  • 盒模型小知识点
  • Hbase-9-HBase操作-过滤器
  • matlab gui编程教程,matlab如何使用gui
  • win10如何禁止CDR软件访问网络的设置方法教程
  • u2 尚硅谷--Vue 脚手架
  • STM32使用库函数点灯实验
  • C# 学习笔记1 - 输入输出
  • 替代STM32的GD32，替代KEIL的Eclipse配置---连载3
  • @angular/forms 源码解析之双向绑定
  • css属性的继承、初识值、计算值、当前值、应用值
  • ES6 学习笔记（一）let，const和解构赋值
  • ES6核心特性
  • IP路由与转发
  • JavaScript 基本功--面试宝典
  • JS笔记四：作用域、变量（函数）提升
  • macOS 中 shell 创建文件夹及文件并 VS Code 打开
  • Making An Indicator With Pure CSS
  • Perseus-BERT——业内性能极致优化的BERT训练方案
  • React的组件模式
  • TCP拥塞控制
  • Vue ES6 Jade Scss Webpack Gulp
  • VUE es6技巧写法（持续更新中~~~）
  • 讲清楚之javascript作用域
  • 聊聊flink的BlobWriter
  • 聊聊springcloud的EurekaClientAutoConfiguration
  • 马上搞懂 GeoJSON
  • 猫头鹰的深夜翻译：Java 2D Graphics, 简单的仿射变换
  • 前端js -- this指向总结。
  • 如何优雅的使用vue+Dcloud（Hbuild）开发混合app
  • 使用common-codec进行md5加密
  • 掌握面试——弹出框的实现（一道题中包含布局/js设计模式）
  • #if和#ifdef区别
  • #ubuntu# #git# repository git config --global --add safe.directory
  • (2022 CVPR) Unbiased Teacher v2
  • （C语言）逆序输出字符串
  • (Matlab)使用竞争神经网络实现数据聚类
  • （PWM呼吸灯）合泰开发板HT66F2390-----点灯大师
  • （九十四）函数和二维数组
  • （三） prometheus + grafana + alertmanager 配置Redis监控
  • （四）Tiki-taka算法（TTA）求解无人机三维路径规划研究（MATLAB）
  • （转）eclipse内存溢出设置 -Xms212m -Xmx804m -XX:PermSize=250M -XX:MaxPermSize=356m
  • (转载)深入super，看Python如何解决钻石继承难题
  • *setTimeout实现text输入在用户停顿时才调用事件！*
  • .NET C#版本和.NET版本以及VS版本的对应关系
  • .net core使用RPC方式进行高效的HTTP服务访问
  • .NET HttpWebRequest、WebClient、HttpClient
  • .net 使用$.ajax实现从前台调用后台方法(包含静态方法和非静态方法调用)
  • .NET（C#、VB）APP开发——Smobiler平台控件介绍：Bluetooth组件