使用kotlin解决这个问题：121. 买卖股票的最佳时机 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。 示例 1： 输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 示例 2： 输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。 提示： 1 <= prices.length <= 105 0 <= prices[i] <= 104

可以使用动态规划的方法来解决此问题。定义状态 dp[i] 表示前 i 天的最大利润，其中第 i 天可以卖出股票，也可以不卖出股票。因此，状态转移方程为：

dp[i] = max(dp[i-1], prices[i]-minPrice)

其中，minPrice 表示前 i 天的最低股票价格。

最终的答案就是 dp 数组中的最大值。

下面是使用 Kotlin 实现的代码：

fun maxProfit(prices: IntArray): Int {
    var minPrice = Int.MAX_VALUE
    var maxProfit = 0
    for (price in prices) {
        minPrice = minOf(minPrice, price)
        maxProfit = maxOf(maxProfit, price - minPrice)
    }
    return maxProfit
}

可以通过以下代码进行测试：

fun main() {
    val prices1 = intArrayOf(7, 1, 5, 3, 6, 4)
    val prices2 = intArrayOf(7, 6, 4, 3, 1)
    println(maxProfit(prices1)) // 5
    println(maxProfit(prices2)) // 0
}

时间复杂度为 O(n)，空间复杂度为 O(1)。

相关问题

使用kotlin完成这个题目：459. 重复的子字符串 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

这道题可以使用字符串匹配的方法来解决。

具体来说，我们可以将原始字符串 s 拼接自身，然后去掉开头和结尾两个字符，这样得到的字符串一定包含原始字符串 s。

接下来，我们可以使用 KMP 算法或者 Z 算法来求出该字符串的前缀函数或者 Z 函数，然后判断原始字符串 s 的长度是否等于这个函数的最后一个值，如果是，说明原始字符串 s 可以由一个子串重复多次构成。

具体实现可以参考以下代码：

fun repeatedSubstringPattern(s: String): Boolean {
    val n = s.length
    val str = s + s
    val pi = IntArray(n * 2)
    var j = 0
    for (i in 1 until n * 2) {
        while (j > 0 && str[i] != str[j]) {
            j = pi[j - 1]
        }
        if (str[i] == str[j]) {
            j++
        }
        pi[i] = j
    }
    return pi[n * 2 - 1] != 0 && n % (n - pi[n * 2 - 1]) == 0
}

其中，`pi` 数组表示字符串 `str` 的前缀函数，`j` 表示匹配的长度，初始值为 `0`。

在循环中，我们不断地向右移动指针 `i`，并且不断地将 `j` 更新为 `pi[j-1]`，直到 `str[i]` 和 `str[j]` 相等，或者 `j` 为 `0`。如果 `str[i]` 和 `str[j]` 相等，我们就将 `j` 增加 1，并且将 `pi[i]` 赋值为 `j`。

最后，我们判断 `pi[n*2-1]` 是否为 0，并且判断 `n` 是否能被 `n-pi[n*2-1]` 整除。如果是，说明原始字符串 s 可以由一个子串重复多次构成，返回 true，否则返回 false。

希望能对你有所帮助！

使用kotlin解决这个问题：283. 移动零 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 请注意 ，必须在不复制数组的情况下原地对数组进行操作。 示例 1: 输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0] 示例 2: 输入: nums = [0] 输出: [0]

以下是使用 Kotlin 解决该问题的代码：

fun moveZeroes(nums: IntArray) {
    var i = 0
    for (j in nums.indices) {
        if (nums[j] != 0) {
            nums[i] = nums[j]
            i++
        }
    }
    for (k in i until nums.size) {
        nums[k] = 0
    }
}

思路：使用双指针，i 表示当前非零元素应该存放的位置，j 表示当前遍历到的位置。遍历数组，如果 nums[j] 不等于 0，将其存放到 nums[i]，然后将 i 加 1，继续遍历。最后，将剩余的位置填充为 0。

例如，对于样例 1 中的 [0,1,0,3,12]，遍历数组，第一个非零元素是 1，应该存放到 nums[0]，然后将 i 加 1，继续遍历。下一个非零元素是 3，应该存放到 nums[1]，然后将 i 加 1，继续遍历。下一个非零元素是 12，应该存放到 nums[2]，然后将 i 加 1，继续遍历。最后，将 nums[3] 和 nums[4] 填充为 0。