1053.交换一次的先前排列

链接：1053.交换一次的先前排列
难度：Medium
标签：贪心、数组
简介：给你一个正整数数组 arr（可能存在重复的元素），请你返回可在 一次交换（交换两数字 arr[i] 和 arr[j] 的位置）后得到的、按字典序排列小于 arr 的最大排列。

题解 1 - cpp

• 编辑时间：2023-04-03
• 执行用时：28ms
• 内存消耗：24.1MB
• 编程语言：cpp
• 解法介绍：找出末尾第一个出现的逆序。

class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& arr) {
        map<int, int> m;
        m[10005] = arr.size();
        for (int i = arr.size() - 1; i >= 0; i--) {
            auto it = m.lower_bound(arr[i]);
            if (m.size() > 1 && it != m.begin()) {
                swap(arr[i], arr[(*(--it)).second]);
                break;
            }
            m[val] = i;
        }
        return arr;
    }
};