VMWARE propel oa 已跪

propel没想到在OA上跪了，40分钟最后一题编程题没写出来，看看大家有有什么想法？

有一个整数数组，要把它变成单调递增或者单调递减（相等也行），可以对数组内任意一个数

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

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

, 3] -> result = 1例子只是对一个数字进行修改。求问思路？

可以对每一组数做一遍单调递增cost计算和单调递减cost计算 然后取cost小的值
单个单调递增只需要扫一遍list 扫到后数比前数小就计算差值 因为最小差值一定是该数和前数之差 前数减和后数加是一个道理 所以扫一遍就可以算出单调递增cost
复杂度O(2n)

只想出个暴力解，遍历数组，以nums[i]为标准，遍历 i的左边和右边，保证是递增或者递减的，计算cost。2 × n ^2 的时间复杂度

priority queue的做法做完test case过了8个 fail了5个

40分钟？不是75分钟的吗

啊哦嗬 发表于 2018-8-21 21:52
40分钟？不是75分钟的吗

我是说花40分钟写这题

是不是可以dp一下。。

被楼主吓得不敢做了

liu5395 发表于 2018-8-21 23:14
被楼主吓得不敢做了

题目随机的

designyyyy 发表于 2018-8-21 22:27
是不是可以dp一下。。

不太懂如何找转移方程啊？

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

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

https://leetcode.com/problems/sliding-window-maximum/ 这个这个算法应该可以解

补充内容 (2018-8-21 23:41):
想错了，请无视

看来题库是真大，毕竟这家OA是代替店面的