首页 > 其他分享 >【LEETCODE】​​1053. 交换一次的先前排列​

【LEETCODE】​​1053. 交换一次的先前排列​

时间:2023-04-03 15:39:46浏览次数:58  
标签:arr 1053 示例 int 交换 排列 先前 LEETCODE

1053. 交换一次的先前排列

难度中等95

给你一个正整数数组 arr(可能存在重复的元素),请你返回可在 一次交换(交换两数字 arr[i] 和 arr[j] 的位置)后得到的、按字典序排列小于 arr 的最大排列。

如果无法这么操作,就请返回原数组。

 

示例 1:

输入:arr = [3,2,1]
输出:[3,1,2]
解释:交换 2 和 1

示例 2:

输入:arr = [1,1,5]
输出:[1,1,5]
解释:已经是最小排列

示例 3:

输入:arr = [1,9,4,6,7]
输出:[1,7,4,6,9]
解释:交换 9 和 7

 

提示:

  • 1 <= arr.length <= 104
  • 1 <= arr[i] <= 104
class Solution {
    public int[] prevPermOpt1(int[] arr) {
        int n = arr.length;
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                int j = n - 1;
                while (arr[j] >= arr[i] || arr[j] == arr[j - 1]) {
                    j--;
                }
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                break;
            }
        }
        return arr;
    }
}

标签:arr,1053,示例,int,交换,排列,先前,LEETCODE
From: https://blog.51cto.com/u_15983387/6166508

相关文章

  • LeetCode 145 二叉树的后序遍历
    LeetCode|145.二叉树的后序遍历给你一棵二叉树的根节点root,返回其节点值的后序遍历。示例1:1\2/3输入:root=[1,null,2,3]输出:[3,2,1]示例2:输入:root=[]输出:[]示例3:输入:root=[1]输出:[1]提示:树中节点的数目在范围[0,10......
  • [leetcode每日一题]4.3
    1053. 交换一次的先前排列提示中等80相关企业给你一个正整数数组 arr(可能存在重复的元素),请你返回可在 一次交换(交换两数字 arr[i] 和 arr[j] 的位置)后得到的、按字典序排列小于 arr 的最大排列。如果无法这么操作,就请返回原数组。 示例1:输入:arr=[3,2,1]输出:[3,1,2]......
  • 【DP】LeetCode 256. 粉刷房子
    题目链接256.粉刷房子假如有一排房子,共n个,每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种,你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。当然,因为市场上不同颜色油漆的价格不同,所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜......
  • leetcode题中的逆向思维——集锦
    417.太平洋大西洋水流问题虽然题目要求的是满足向下流能到达两个大洋的位置,如果我们对所有的位置进行搜索,那么在不剪枝的情况下复杂度会很高。因此我们可以反过来想,从两个大洋开始向上流,这样我们只需要对矩形四条边进行搜索。搜索完成后,只需遍历一遍矩阵,满足条件的位置即为两个......
  • leetcode 394.字符串解码 Java
    394.字符串解码给定一个经过编码的字符串,返回它解码后的字符串。编码规则为:k[encoded_string],表示其中方括号内部的encoded_string正好重复k次。注意k保证为正整数。你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。此外......
  • leetcode 739.每日的温度 Java
    739.每日的温度给定一个整数数组temperatures,表示每天的温度,返回一个数组answer,其中answer[i]是指对于第i天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用0来代替。示例1:输入:temperatures=[73,74,75,71,69,72,76,73]输出:[1,1,4,2,1,......
  • leetcode 20. 有效的括号 Java
    给定一个只包括'(',')','{','}','[',']'的字符串s,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。示例1:输入:s="()"输出:true示例2:输入:s="()[]{}"输出:true......
  • Leetcode(剑指offer专项训练)——DP专项(6)
    排序的数目题目给定一个由不同 正整数组成的数组nums,和一个目标整数target。请从nums中找出并返回总和为target的元素组合的个数。数组中的数字可以在一次排列中出现任意次,但是顺序不同的序列被视作不同的组合。题目数据保证答案符合32位整数范围。链接无效DFS......
  • Leetcode(剑指offer专项训练)——DP专项(5)
    最少的硬币数目给定不同面额的硬币coins和一个总金额amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。你可以认为每种硬币的数量是无限的。链接完全背包问题思路:主要是要自己推出动态转移方程\[F(i)=mi......
  • 【DP】LeetCode 64. 最小路径和
    题目链接64.最小路径和思路分析动态规划题目的时候只需要考虑最后一个阶段,因为所有的阶段转化都是相同的,考虑最后一个阶段容易发现规律表示状态假设到了右下角,考虑一下我们要存储的信息走到最后坐标的最小步数当前坐标的信息,用来判断是否走到了右下角很容易联想到使用......