OA遇到个难题，请教各位

果然遇到这道题，感觉好难。不多说，先贴出来，请大家广泛讨论。原题目很长，一下是我理解的题意。Make changes to an array to a non-descending order or non-ascending order, counts the minimum changes to achieve this.
Example 1:
input = [9,7,6,1,4,4]  you have to change 1 to 4 to make it non-ascending order array  [9,7,6,4,4,4]

output=3

Example 2:
input = [1,3,3,3,3,3,9,8], change the last element 8 to 9, to make the array non-descending order
output = 1


我之前听人说这是个DP题，无奈想不通。就瞎写了个，排序之后求diff，加在一起，也不知道如何证明正确或者错误。。求各位大神指教。

public static int getMinChange(int[] inputs,int k) {

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

b">1 - i]){
            resDes += inputs[i] - copy[inputs.length - 1 - i];
        }
    }

    return Math.[i]min(resAsc,resDes);
}

我觉得是dp吧？前面i-1个人数组排好序的情况下，使前i个排好序的cost是修改arr[i]的量。ascend来一遍descend来一遍，取两种scenario的dp[n]的值小的那个

关注一下，不知道有没有大神指教

基本上原题
https://www.geeksforgeeks.org/minimum-incrementdecrement-to-make-array-non-increasing/

用min heap 分两种情况讨论 不递增或者不递减 然后取最小值

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

wojiushieyu 发表于 2019-3-15 10:29
谢谢分享。
看懂了这个代码，但是不太明白你说的用两个min heap， 难道不是min heap求 non increasing,  ...

就是两个heap啦 就是这个意思

LZ, 这是90分钟一道题吗？