首页 > 试题广场 >

最小金额购买商品

[编程题]最小金额购买商品
  • 热度指数：1093 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

有一排商品，每一个商品都有自己的价值，现在需要花一定金额购买这些商品。规则是：如果一个商品的价值比它旁边的一个商品要高，那么这个商品就必须比它旁边的商品花费更多金额。所有的商品至少要进行一次金额购买。假设一次购买花费金额单位为1，最少需要多少金额可以购买所有商品？

现给定一个数组，数组元素表示每个商品的价值。请编写代码输出最少需要花费的金额。

示例1

输入

[1,0,2]

输出

5
算法知识视频讲解
添加回答
pein531头像 pein531
贪心算法，先将所有商品的花费初始化为1。从左往右遍历一遍，检查当前位置商品的花费相较于左邻居是否合理，不合理就以最小限度超过它；再从右往左遍历一遍，检查当前位置商品的花费相较于右邻居是否合理，不合理也以最小限度超过它。最后将所有商品的花费累加起来即可。 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型
     */
    public int cost (int[] array) {
        // write code here
        int n = array.length;
        int[] cost = new int[n];
        Arrays.fill(cost, 1);
        for(int i = 1; i < n; i++){
            if(array[i] > array[i - 1] && cost[i] <= cost[i - 1])
                cost[i] = cost[i - 1] + 1;
        }
        for(int i = n - 2; i >= 0; i--){
            if(array[i] > array[i + 1] && cost[i] <= cost[i + 1])
                cost[i] = cost[i + 1] + 1;
        }
        int res = 0;
        for(int i = 0; i < n; i++) res += cost[i];
        return res;
    }
}

发表于 2021-08-29 22:54:06 回复(1)
YXXY头像 YXXY
难道就我一个没看懂题目的吗。。。
我太菜了
发表于 2021-09-01 11:40:44 回复(9)
hun2i头像 hun2i
贪心，从左往右遍历计算当前值左边有几个连续比它低的值个数，再从右往左遍历计算当前值右边又有几个连续比它低的值个数，那么当前值最终的价格应该是max(左边个数，右边个数)，最后累加起来就是总共需要的金额，描述的有点差，看代码🙂 
int cost(vector<int>& array) {
    int len = array.size();
    vector<int> l(len, 1);
    vector<int> r(len, 1);
    for(int i = 1; i < len; i ++)
        if(array[i] > array[i - 1])
            l[i] = l[i - 1] + 1;
    for(int i = len - 2; i >= 0; i --)
        if(array[i] > array[i + 1])
            r[i] = r[i + 1] + 1;
    int res = 0;
    for(int i = 0; i < len; i ++)
        res += max(l[i], r[i]);
    return res;
}
编辑于 2021-08-30 16:25:14 回复(1)
牛客96796454号头像 牛客96796454号 
class Solution: def cost(self, array): # write code here  length = len(array)
        cost_list = [1] * length for i in range(1, length): if array[i] > array[i - 1] and cost_list[i] <= cost_list[i - 1]:
                cost_list[i] = cost_list[i - 1] + 1  for i in range(length - 2, -1, -1): if array[i] > array[i + 1] and cost_list[i] <= cost_list[i + 1]:
                cost_list[i] = cost_list[i + 1] + 1  # print(array)  # print(cost_list)  cost = sum(cost_list) return cost
发表于 2022-08-23 22:42:11 回复(0)
菲尼克斯弗兰克头像 菲尼克斯弗兰克
leetcode-135分发糖果问题
发表于 2022-07-02 17:58:29 回复(2)
数往者顺头像 数往者顺
就是如果比左边商品贵，那么就在本身价格上再加一块，如果比两边都贵，就加两块。好无语的描述题目
发表于 2022-03-19 17:14:27 回复(0)
牛客420004639号头像 牛客420004639号
楼上各位，有没有一种可能，不需要那么多次for循环。 
class Solution:
    def cost(self , array ):
        cost = [1] * len(array)
        for i in range(1, len(array) ):
            if array[i]>array[i-1]:
                cost[i]=cost[i-1]+1     
        if array[0]>array[1]:
            cost[0]=cost[1]+1  
        return sum(cost)


发表于 2022-03-16 02:20:17 回复(0)
tttt111头像 tttt111
java 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型
     */
    public int cost (int[] array) {
        // write code here
        int count=0;
        int meansure=0;
        int min=0x3f3f3f3f;
        int len=array.length;
        for(int i=1;i<len;i++)
        {
            if(array[i]>array[i-1])
                meansure++;
            else if(array[i]<array[i-1])
                meansure--;
            count+=meansure;
            min=Math.min(min,meansure);
        }
        if(min<0)
            count+=Math.abs(min)*len;
        count+=len;
        return count;
    }
}

思路很简单一看就懂
发表于 2021-09-30 20:26:37 回复(0)
牛客269980930号头像 牛客269980930号
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param array int整型一维数组 
# @return int整型
#
class Solution:
    def cost(self , array ):
        s = len(array)*[1]
        for i in range(1,len(array)):
            if array[i]>array[i-1]:
                s[i] = s[i-1] + 1
        for i in range(len(array)-1,0,-1):
            if array[i]<array[i-1]:
                s[i-1] = s[i] + 1
        return sum(s)
        # write code here
发表于 2021-09-07 15:57:00 回复(0)
JavaScript
牛客907378159号头像 牛客907378159号
function cost( array ) {
    let cost=0;
    let all=[];
    let len=array.length;
    all=array.map((a,b,arr)=>{
        if(a<=arr[b-1]&&b==arr.length-1) return 1;
        if(a<=arr[b+1]&&b==0) return 1;
        if(a<=arr[b-1]&&a<=arr[b+1]&&b!=0&&b!=arr.length-1) return 1;
        return 0;
    });
    all=all.map((item,index,arr)=>{
        if(item==0){
            return Math.max((arr.indexOf(1,index+1)-index+1),(index-arr.lastIndexOf(1,index-1)+1));
        }else{
            return 1;
        }
    });
    cost=all.reduce((pre,item)=>pre+=item,0);
    return cost;
}
发表于 2021-09-07 15:17:51 回复(0)
天有些蓝头像 天有些蓝
设定一个初始值，然后从左向右扫描，右大于左就加1，小于就减1，等于就不变，最后把最小值补齐至1，再求和。 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param array int整型一维数组 
# @return int整型
#
class Solution:
    def cost(self , array ):
        # write code here
        dp = [1]*len(array)
        for i in range(1,len(array)):
            if array[i]>array[i-1]:
                dp[i] = dp[i-1]+1
            elif array[i]==array[i-1]:
                dp[i] = dp[i-1]
            else:
                dp[i] = dp[i-1]-1
        min_v = min(dp)
        add_v = 1-min_v
        res = sum(dp)+add_v*len(dp)
        return res


发表于 2021-09-05 20:52:33 回复(0)
牛客511771125号头像 牛客511771125号
C++ 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param array int整型vector
     * @return int整型
     */
    int cost(vector<int>& array) {
        // write code here
        int n = array.size();
        vector<int> l2r(n), r2l(n);
        l2r[0] = 1, r2l[n - 1] = 1;
        int count = 1;
        for (int i = 1; i < n; ++i) {
            if (array[i] > array[i - 1]) count++;
            else count = 1;
            l2r[i] = count;
        }
        count = 1;
        for (int i = n - 2; i >= 0; --i) {
            if (array[i] > array[i + 1]) count++;
            else count = 1;
            r2l[i] = count;
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += max(l2r[i], r2l[i]);
        }
        return ans;
    }
};


发表于 2021-08-31 20:15:21 回复(0)
牛客853297935号头像 牛客853297935号 
public int cost (List<int> array) {
        int[] cost = new int[array.Count];
        int offset = 0;
        cost[0] = 1;
        for (int i = 1; i < array.Count; i++)
        {
            if (array[i] > array[i - 1])//右边大
            {
                cost[i] = cost[i - 1] + 1;
            }
            else if(array[i] == array[i - 1])
            {
                cost[i] = cost[i - 1];
            }
            else//右边小
            {
                cost[i] = cost[i - 1] - 1;
                if ((cost[i] + offset) == 0)
                {
                    offset++;
                }
            }
        }
        int sum = 0;
        for (int i = 0; i < cost.Length; i++)
        {
            sum += cost[i];
        }
        sum += cost.Length * offset;
        return sum;
    }
代码如上。
    
发表于 2021-08-26 18:02:37 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 算法工程师 PHP工程师 虾皮信息 游戏研发工程师 大数据开发工程师 Java工程师
上传者：小小
难度：
13条回答 2654浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号