[LintCode] Replace With Greatest From Right

xiaokai 发布于2019-08-15 17:49 / 2952人阅读

Problem

Given an array of integers, replace every element with the next greatest element (greatest element on the right side) in the array. Since there is no element next to the last element, replace it with -1. For example, if the array is [16, 17, 4, 3, 5, 2], then it should be modified to [17, 5, 5, 5, 2, -1].

Example

Give nums = [16, 17, 4, 3, 5, 2], change nums to [17, 5, 5, 5, 2, -1]
You should do it in place.

Solution

public class Solution {
    /**
     * @param nums: An array of integers.
     * @return: nothing
     */
    public void arrayReplaceWithGreatestFromRight(int[] nums) {
        // Write your code here.
        int n = nums.length-1;
        int max = nums[n];
        nums[n] = -1;
        for (int i = n-1; i >= 0; i--) {
            int cur = nums[i];
            nums[i] = max;
            max = Math.max(max, cur);
        }
        return;
    }
}

GPU云服务器云服务器 Greatest LintCode right LintCode134_LRU

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69465.html

[LintCode/LeetCode] Lowest Common Ancestor of BST/

摘要：递归左右子树，若左右子树都有解，那么返回根节点若仅左子树有解，返回左子树若仅右子树有解，返回右子树若都无解，返回。对于而言，更为简单公共祖先一定是大于等于其中一个结点，小于等于另一个结点。 Problem Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the ...

dinfer 2019-08-14 15:33 评论0 收藏0
LintCode: Max Tree

摘要：题目此题和很类似，所以第一反应使用递归做。递归的解法过不了，会显示超时比递归的更好的方法是用，比较难想到，代码参考了思路是用一个单调递减栈寻找最大值。这个操作可以帮我们顺利找到左子树和父节点。题目 Given an integer array with no duplicates. A max tree building on this array is defined as fol...

ivan_qhz 2019-07-30 14:42 评论0 收藏0
LintCode Coins in a line III

摘要：复杂度思路参考的思路，对于，表示在从到的范围内，先手玩家能拿到的最大的硬币价值。对于状态，先手玩家有两种选择，要么拿的硬币，要么拿的硬币左边一个的或者右边一侧的，如果拿左侧的硬币，如果拿右侧的硬币，取两个值的最大值。 LintCode Coins in a line III There are n coins in a line. Two players take turns to ...

focusj 2019-08-14 15:03 评论0 收藏0
[LintCode] Segment Tree Query I & Segment Tree

摘要：题目是要查询到这个区间内某一点的。值是从最底层的子节点值里取最大值。因此，不用太复杂，递归就可以了。与所不同的是，对所给区间内的元素个数求和，而非筛选。这样就会出现的情况，视作本身处理。 Segment Tree Query Problem For an integer array (index from 0 to n-1, where n is the size of this ar...

vibiu 2019-08-14 16:22 评论0 收藏0