逆向工作法：

逆向工作法，就是逆向思维，通过将问题反向思考求解。
逆向工作法用到了栈的思想，但不需要栈也能实现。

例题：

给定一个编码字符串 S。为了找出解码字符串并将其写入磁带，从编码字符串中每次读取一个字符，并采取以下步骤：

如果所读的字符是字母，则将该字母写在磁带上。
如果所读的字符是数字（例如 d），则整个当前磁带总共会被重复写 d-1 次。现在，对于给定的编码字符串 S 和索引 K，查找并返回解码字符串中的第 K 个字母。

示例 1：

输入：S = "leet2code3", K = 10
输出："o"
解释：
解码后的字符串为 "leetleetcodeleetleetcodeleetleetcode"。
字符串中的第 10 个字母是 "o"。

示例 2：

输入：S = "ha22", K = 5
输出："h"
解释：
解码后的字符串为 "hahahaha"。第 5 个字母是 "h"。

示例 3：

输入：S = "a2345678999999999999999", K = 1
输出："a"
解释：
解码后的字符串为 "a" 重复 8301530446056247680 次。第 1 个字母是 "a"。

提示：

2 <= S.length <= 100
S 只包含小写字母与数字 2 到 9 。
S 以字母开头。
1 <= K <= 10^9
解码后的字符串保证少于 2^63 个字母。

来源：力扣（LeetCode）第880题

链接：https://leetcode-cn.com/problems/decoded-string-at-index

解析：

首先先把题目要求的总长度算出来，这个比较容易，难点在于如何将第K个数从总长度中找出来。因为我们无法将整个数组都写出来，比如实例3，a的个数太多了，会导致内存不够的。所以我们只能找一种办法，在不用写出全部数组的情况下将第K个元素算出来。

如果每次都从前面思考，你会发现自己陷入瓶颈，找不到合适的方法满足要求。

可是如果反过来思考一下。我们刚才算出总长度用的方法是遍历数组，遇到字母+1，遇到数字就乘以这个数字。现在我们反过来思考，我们从后往前遍历，总长度遇到字母-1，遇到数字就除以这个数字。

假设我们遇到数字3，说明剩下的数字的总长度一定能正好分成3份，如果总长度是36，那么也就是说只有12个不同的答案，因为每一份的字母都是一样的。此时总长度为12，因此我们将K % 总长度12 ，看一下这个值是否等于0。如果不等于0，并且不是数字，就-1，直到K % 总长度 == 0，那么遍历到这个位置的S[i]就是所要求的元素。

上代码看一下：

先来一个不用栈实现的官方解法

class Solution:
def decodeAtIndex(self, S: str, K: int) -> str:
    size = 0
    for c in S:
        if c.isdigit():
            size *= int(c)
        else:
            size += 1

    for c in reversed(S):
        K %= size
        if K == 0 and c.isalpha():
            return c
        if c.isdigit():
            size /= int(c)
        else:
            size -= 1

然后是使用栈实现的，其实是一样的，从后往前遍历就是在模拟出栈，不过不用真的出栈，节省了时间

class Solution(object):
def decodeAtIndex(self, S, K):
    stack = []
    add = 0
    for i in range(len(S)):
        if S[i].isdigit():
            add *= int(S[i])
        else:
            add += 1
        stack.append(S[i])
    while stack:
        K = K % add
        if K == 0 and stack[-1].isalpha():
            return stack[-1]
            
        if stack[-1].isdigit():
            add = add // int(stack.pop())
        else:
            add -= 1
            stack.pop()

复杂度分析：

时间复杂度：O(N)，其中 N 是 S 的长度。
空间复杂度：O(1)。

总结：

根据题目所给的条件，来反向推导题目，有可能获得意想不到的效果。