你需要按照以下要求，帮助老师给这些孩子分发糖果：
那么这样下来，老师至少需要准备多少颗糖果呢？
示例 1:
输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2:
输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
先看题目要求，
1.每个孩子至少分配到 1 个糖果。
2.相邻的孩子中，评分高的孩子必须获得更多的糖果。
总的糖果最少
总结我们所有可能会遇到的情况，总的解决方法就是首先保证1越多越好，能发一个最好，之后以相差1的情况发放。
每个孩子至少一个糖果，那么什么样的情况孩子会得到一个糖果呢？
当这个孩子i，ratings{i] >ratings[i-1]，且ratings{i] <ratings[i+1]，边界可以单独考虑，简而言之就是处于“低谷”，“波谷”，以数学上的话来说，是函数的极小值。除此之外呢？
还有一种情况，连续的相同的值，而且是有条件的，例如，[1，2，3，3，2，1]，这种情况两个3处是1吗，不是，[1，2，3，3，3，2，1]，这种情况呢？
实际上，判断是不是发一个，可以这样想，如果上升之后就下降，就不是了，如果停留了，那可能是。
还有便是，连续的变化的时候，就是单调递增和递减时，以初始值为1，公差为 1 的等差数列发放
具体考虑便是，当单调递增时，初始值为1，当前发放的糖果比前一个多一个，如果到达了波峰，最高点，有可能下一个值补是最大值，有可能还是。
当不是最大值，意味着走“下坡路”了，此时，我们需要知道当前下降趋势走到了哪？将走到的地方记做极小值，此处发放一个糖果，以1的等差数列逆推之前的发放糖果数
如果还是最大值，但下一个不是最大值，其实处理方法跟之前一样
但是下下一个值还是最大值呢，那么下一个最大值为1
以几个个例子来看：
[1,2,3,2,1] ==> [1,2,3,2,1]
[1,2,3,3,2,1] ==> [1,2,3,3,2,1]
[1,2,3,3,3,2,1] ==> [1,2,3,1,3,2,1]
[1,2,3,3,3,3,3,2,1] ==> [1,2,3,1,1,1,3,2,1]
首先用第一种方法，这种方法其实不是第一次用了，接雨水有一个方法和这个类似
使用两个vector<int>left,vector<int>right
一种从左到右记录“单调递增的序列”，实际是ratings的单调递增序列(从左到右)
另一种从右到左记录“单调递增的序列”，实际是ratings的单调递减序列(从左到右)
先举个例子：
ratings: [1,2,3,3,2,1,0,1,3,2,1]
left:[1,2,3,1,1,1,1,2,3,1,1]
right: [1,1,1,4,3,2,1,1,3,2,1]
汇总时，取两者的最大值就可以了
下面是程序：
这是提交结果：
由于提交有了一段时间，实际结果是，时间上还不错，但是空间上不佳
补：left[i]=1，这个地方似乎可以一开始给left赋初值。
接下来，我们使用另一种方法，不使用两个vector，边遍历边处理，过程稍微复杂了一点
具体过程和思路中基本一致，部分细节上有些差别，都在程序的注释里面了
下面是程序：
下面是系统结果：
空间上有明显改善。
广大程序员都喜欢用leetcode刷题，方便，权威
在开始我们的leetcode之路前，我们需要了解下leetcode是什么？为什么叫leetcode呢 ？
摘自百度百科：
力扣（LeetCode）是领扣网络旗下专注于程序员技术成长和企业技术人才服务的 品牌 。源自美国硅谷，力扣为全球程序员提供了专业的IT技术职业化提升平台，有效帮助 程序员 实现快速进步和长期成长。 [1-4]
此外，力扣（LeetCode）致力于解决程序员 技术评估 、培训、职业匹配的痛点，逐步引领 互联网技术 求职和招聘迈向 专业化 。
领扣网络？
从其他地方找到了对领扣网络的介绍
领扣网络（lingkou.com）是一家专注程序员技术提升和企业技术人才服务的科技公司。源自美国硅谷，为全球程序员提供专业的IT技术职业化提升平台，致力于解决程序员技术成长、评估、职业匹配的痛点，逐步引领互联网技术求职和招聘迈向专业化
网站无法打开，不知道怎么回事
*最近在做一些 leetcode 的算法题，我会将自己做过的算法题记录下来以供大家参考，如果查找不方便请看 油猴插件实现网站左侧目录生成。
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例：
解答：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例：
提示：
解答：
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例：
说明:
解答：
给定一个整数数组，判断是否存在重复元素。
如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
示例：
解答：
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例：
解答：
给定两个数组，编写一个函数来计算它们的交集。
示例：
说明：
进阶:
解答：
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例：
解答：
给定一个数组 nums ，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
说明:
给定一个整数数组 nums 和一个目标值 target ，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例：
解答：
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例：
说明:
解答：
给定一个 *n *× *n* 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。 请不要 使用另一个矩阵来旋转图像。
示例：
解答：
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须 原地修改输入数组 、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例：
解答：
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例：
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
解答：
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
示例：
解答：
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
长度一样，包含的字母都一样，每个字符出现的频率也一样，只是顺序不同而已，这就属于异位词，
示例：
说明:
你可以假设字符串只包含小写字母。
进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
解答：
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明 ：本题中，我们将空字符串定义为有效的回文串。
示例：
解答：
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
注意 ：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。
提示 ：
示例：
解答：
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始) 。如果不存在，则返回 -1 。
示例：
说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符
解答：
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：
1 被读作 "one 1" ("一个一") , 即 11 。
11 被读作 "two 1s" ("两个一") , 即 21 。
21 被读作 "one 2", "one 1" ("一个二" , "一个一") , 即 1211 。
给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。
注意 ：整数序列中的每一项将表示为一个字符串。
示例：
解答：
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 "" 。
示例：
说明:
所有输入只包含小写字母 a-z 。
解答：
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
现有一个链表 -- head = [4,5,1,9]，它可以表示为:
示例：
说明：
解答：
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
解答：
反转一个单链表。
示例：
解答：
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
解答：
请判断一个链表是否为回文链表。
示例：
解答：
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1 ，则在该链表中没有环。
示例：
解答：
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明 : 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7] ，
返回它的最大深度 3 。
解答：
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
示例：
解答：
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
解答：
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树： [3,9,20,null,null,15,7] ,
返回其层次遍历结果：
解答：
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例：
给定有序数组: [-10,-3,0,5,9] ,
一个可能的答案是: [0,-3,9,-10,null,5] ，它可以表示下面这个高度平衡二叉搜索树：
解答：
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
说明:
示例:
解答：
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n] ，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例：
解答：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意 ：给定 n 是一个正整数。
示例：
解答：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意 ：你不能在买入股票前卖出股票。
示例：
解答：
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
解答：
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例：
解答：
打乱一个没有重复元素的数组。
示例：
解答：
设计一个支持 push ， pop ， top *** 作，并能在常数时间内检索到最小元素的栈。
示例：
解答：
写一个程序，输出从 1 到 n 数字的字符串表示。
示例：
解答：
统计所有小于非负整数 n 的质数的数量。
示例：
解答：
给定一个整数，写一个函数来判断它是否是 3 的幂次方。
示例：
解答：
罗马数字包含以下七种字符: I ， V ， X ， L ， C ， D 和 M 。
例如，罗马数字 2 写做 II ，即为两个并列的 1 。 12 写做 XII ，即为 X + II 。 27 写做 XXVII , 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII ，而是 IV 。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX 。这个特殊的规则只适用于以下六种情况：
示例：
解答：
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量 ）。
示例：
提示：
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）